ソースとターゲットが同じグラフ内の2つのノード間の最短経路を計算する方法は？

グラフ：例えば

A->B(5) 
A->D(5) 
A->E(7) 
B->C(4) 
C->D(8) 
C->E(2) 
D->C(8) 
D->E(6) 
E->B(3)

BとBとの間の最短経路は何ですか？私はdijkstraを使用しようとしましたが動作しませんでした。最初のステップでは常にB-> Bを返します。

正しいANS：B-> C-> E-> B

「X-> Bからの最短パスは何ですか？エッジB-> Xが存在する任意のノードXに対して、それらの最小値をとり、B-> Xを加えます。 – DSM

スプリット2に頂点：B1とB2、元のグラフにBで開始すべてのエッジがB1で開始します。 Bで終了するすべてのエッジはB2で終了します。

その後、Dijkstraを実行して、変更されたグラフのB1からB2までの最短経路を見つけることができます。

注：グラフのすべてのパスを保存する場合は、エッジB2-> B1を追加します。サイクルサーチの結果は変更されず、元のグラフと変更されたグラフのすべてのパスは等価になります

2012-04-13 07:57:38 voidengine

答えて