0

how to calculate the shortest path between two nodes in a graph where the source and target are the same?

Graph:

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)

for example what is the shortest path between B and B? I tried to use dijkstra but didn't work, it always return B->B in the first step.

correct ans: B->C->E->B

4

1 に答える 1

0

頂点を B1 と B2 の 2 つに分割します。元のグラフの B で始まるすべてのエッジは B1 で始まります。B で終了するすべてのエッジは B2 で終了します。

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

注:グラフ内のすべてのパスを保持する場合は、追加のエッジ B2->B1 を追加します。それによってサイクル検索の結果が変わることはなく、元のグラフと変更されたグラフのすべてのパスは同等になります。

于 2012-04-13T07:57:38.360 に答える