如何計算圖形中源和目標相同的兩個節點之間的最短路徑？

圖：

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->乙

難道你不能問「從X-> B的最短路徑是什麼？」對於存在邊B-> X的任何節點X，取其中的最小值，並添加B-> X？ – DSM 2012-04-13 03:18:48

分割頂點爲兩個：B1和B2，在那裏，在乙在原始圖發表的所有邊緣將在B1開始;以B結尾的所有邊將在B2中終止。

之後，您可以運行Dijkstra以找到修改圖中從B1到B2的最短路徑。

注意：如果要保留圖中的所有路徑，請添加額外的邊B2-> B1。這不會改變你的循環搜索的結果，並且原始和修改圖表中的所有路徑將是等效的

2012-04-13 07:57:38 voidengine

回答