算法根據距離源的距離對圖中的頂點進行排序

Question

我在數據結構課程中遇到以下問題，如果我的解決方案是正確的，我希望知道。 （V，E）是一個連通的無向圖，使得| V | = m且| E | = n。每個頂點都有其唯一的名稱（從1到n）。現在給定一個源頂點S，我需要按照它們與S的距離對所有頂點進行排序，然後將它們打印出來。複雜性O（M + N）

我的解決辦法（理論值）：

我將基本使用BFS僞代碼，我將在while循環的結束畫之前添加下面的命令，例如當前頂點「u」黑色：

入隊（Q2，u）。

然後我將有一個排序的隊列Q2，我可以打印。

您認爲它的正確性？ 非常感謝！

Answer 1

如果您的邊緣是成本加權的，那麼您將需要使用Dijkstra算法而不是寬度優先。否則，是的，該方法是好的。

Answer 2

您描述的問題由Dijkstra algorithm解決。它主要負責最接近尚未訪問節點，並寫入到最接近的所有節點的距離吧：

1. start from the source node S 
2. add all neighboring nodes into a list, ordered by their distance 
    and write down the current shortest distance to them 
3. pick the closest node N 
4. update the distances of all already visited nodes, if a shorter distance 
    is available to them through N 
5. add remaining neighboring nodes into the list 
6. eliminate N from the list and repeat from step 3. 

這是必要的，您訪問節點從最近一到最遠的順序，那麼你不會錯過任何可能的最短路徑。

實現Dijkstra的挑戰是優先級前端的實現，該前端存儲節點，按距離源的距離排序。如果使用簡單列表，則還需要考慮將新節點輸入到數組中，因爲需要查找元素的正確位置。

因此，基本的Dijkstra有多種改進，例如使用Fibonacci heap作爲實現優先級隊列的結構。