グラフの最小ウェイトパス

Question

私は重み付けグラフを持っています。 ノードSからノードEまでの最適なパスを見つけたいので、そのパス内にあった最大単一エッジの重みが可能な限り小さくなります。例えば

：このグラフの

S -> E (w=40) 
S -> A (w=30) 
A -> E (w=20) 

、djikstraは、コストと（S->コスト40とE私が代わりに欲しい、であるS-> A-> Eであることを最短経路を計算しますmax（30,20）= 30）。

ダイクストラをこのように変更することはできますか？ これを実現する既知のアルゴリズムはありますか？

Answer 1

この問題を解決する方法は、プライオリティキュー/ヒープからの距離（比較値）を保存する方法を変更することですが、それ以外の場合、構造はDijkstra'sに似ています。あなたは全体の距離ではなく、構築されたパスにこれまでの最大の重みを格納します。この方法では、優先順位のキューでは、最小のものを優先して順番に実行します。

したがって、あなたが与えた例では、それは30のawともう1つの40のためにS - > Aで始まります。2番目の実行では、A = EはMath.max（20,30）が< 40であるため、優先キュー/ヒープに先に格納されるためです。

宛先に到達すると、そのパスが最も少なくなることが保証されます。これが理にかなってほしい！

1）すべてのエッジを削除し、ソート最初の分とエッジ：

Answer 2

あなたは貪欲アルゴリズムのバリアントを使用することができます。

2）ソースノードからターゲットノードへのパスがあるまで、最小から最大の順にグラフにエッジを追加します。そのパスはあなたが探しているパスです。