Dijkstra的算法不會生成最短路徑？

Question

我正在通過使用Dijkstra算法的最短路徑問題。我遇到了麻煩，因爲算法應該提供最短路徑，但是在運行算法之後，我手工獲取了一條短路徑。這只是這個算法的副產品嗎？

我想產生的路徑是從 - >ž

這裏是我從每個頂點應用算法，以最短的距離跳得到我訪問路徑：

2 4 2 2 1 2 1 1 8  = 23 
a -> d -> g -> k -> r -> n -> q -> p -> t -> z 

這是令人困惑的我，因爲如果我走這條路：

4 2 2 2 2 2 2  = 16 
a -> c -> f -> i -> m -> p -> s -> z 

我得到的距離比算法產生的距離小5。

我在某處失足了嗎？

Answer 1

看起來像你誤解Dijkstra算法的工作原理。不必在每個節點上採用權重最小的邊，而是始終需要考慮從起始點（節點$ a $）開始的總距離。您保留了一堆所有可能的路徑，這些路徑始於只有沒有邊的起始節點，並且通過添加所有路徑並將每個路徑添加到當前在每個步驟中考慮的路徑的每個傳出邊緣來擴展。

這是一堆試圖總結出錯的地方。我建議重讀Dijkstra算法如何工作的：http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm