使用dijkstra從隊列中彈出最短路徑的節點

我有一個使用正確實現的dijkstra算法計算出的最短路徑。它通過B，C，D和E從A到F，因此整個最短路徑是[A，B，C，D，E，F]。使用dijkstra從隊列中彈出最短路徑的節點

現在我想從G到F.當從隊列中彈出C時，我意識到它是到F的最短路徑的一部分。這是否意味着我也知道從G到F的最短路徑是[ G，H，C，D，E，F]？

2015-08-28 marcus

號但它確實意味着從Ç到˚F的最短路徑爲[C，d，E，F]。

如果存在較短的路徑，則我們構造一個從A到F [A，B，[P]]的新路徑，它比我們的原始路徑固有地更短。這是一個矛盾，因爲我們認爲[A，B，C，D，E，F]是從A到F的最短路徑。

這可以推廣以證明最短路徑的子路徑也是最短的路徑。在你的情況下，這意味着如果從G到F的最短路徑包含C，那麼最短路徑包含[C，D，E，F]作爲子路徑。既然你不知道C是否在你的最短路徑，這個定理只會幫助你減少計算次數，如果你存儲從C到F的最短路徑的權重。

2015-08-28 12:53:14

這可能是人們通常在繪製圖表時也會花費成本的原因。顯然我 - > F可以例如是6，C - > F也是6，H - > 1.我的不好。多謝你們。 – marcus

我想不會，因爲你必須要在考慮從H到C. 的距離，如果該距離[H，C]是巨大的，比方說大於距離[H更大，我，F]？

2015-08-28 12:51:49

但是如果[H，I，F]會比[H，C]短，我會在從隊列中彈出C之前到達F？！ – marcus

但我認爲[H，I]的權重大於[H，C]，但路徑的其餘部分[I到F]的權重小於[C，D，E，F] –

我同意。我的例子很糟糕，但我認爲邁克爾評論中的那個人是正確和澄清的。 –

回答