Dijkstra演算法

習題預習

1. 在下圖中，使用Dijkstra’s Algorithm計算從節點A到節點F的最短路徑。

2. 節點A、B、C、D、E、F、G連為一棵樹，各自與相鄰節點間有權重，使用Dijkstra’s Algorithm計算從節點A到節點G的最短路徑。

3. 在下圖中，使用Dijkstra’s Algorithm計算從節點A到節點J的最短路徑。

4. 考慮以下加權連通無向圖。使用Dijkstra’s Algorithm計算從節點A到節點I的最短路徑。

5. 考慮以下加權有向圖。使用Dijkstra’s Algorithm計算從節點A到節點G的最短路徑。

請注意，這些問題中的圖形可能有其他邊或節點，但為了簡化問題，它們未顯示。對於這些問題，您需要先使用Dijkstra’s Algorithm計算出每個節點到源節點的最短路徑。

說明知識

Dijkstra’s Algorithm是一種用於尋找最短路徑的演算法，通常用於計算機科學，特別是網路路由和GPS導航等應用中。

這個演算法的主要思想是，尋找從起點到終點的最短距離，如果路徑經過的節點有邊權重（也稱為距離）之和最小，那麼該路徑就是最短路徑。Dijkstra算法通過對整個圖進行BFS搜尋，以距離值作為優先順序，計算出從起點到所有節點的距離。

以下是Dijkstra算法尋找從節點A到節點J的最短路徑的步驟：

1. 創建一個距離矩陣，設置所有節點的初始距離為無限大，除了起點，它的距離為0。

2. 選擇起點A，並將其加入到一個已訪問的集合中。

3. 對A周圍可到達節點的距離進行更新，這些節點的距離設置為A的距離加上從A到其它節點的距離。

4. 從距離矩陣中選擇距離最短的節點，將其添加到已訪問的集合中。

5. 重複3和4，直到所有節點都被檢查並且在距離矩陣中更新了最短距離。

以下是一個例子，如圖所示，我們要找到從節點A到節點J的最短路徑。

1. 創建距離矩陣，設置所有節點的初始距離為無限大，除了起點A，它的距離為0。

2. 選擇起點A，將其添加到已訪問的集合中。

3. 將起點A的距離更新周圍可到達節點的距離，節點D的距離為3，節點B的距離為5，節點C的距離為9。

4. 從距離矩陣中選擇距離最短的節點D，將其添加到已訪問的集合中。

5. 將節點D的距離更新周圍可到達節點的距離，節點E的距離為6，節點B的距離依然是5，節點C的距離為9。

6. 從距離矩陣中選擇距離最短的節點B，將其添加到已訪問的集合中。

7. 將節點B的距離更新周圍可到達節點的距離，節點C的距離為8，節點F的距離為10，節點E的距離為12。

8. 從距離矩陣中選擇距離最短的節點C，將其添加到已訪問的集合中。

9. 將節點C的距離更新周圍可到達節點的距離，節點F的距離為14，節點E的距離為11。

10. 從距離矩陣中選擇距離最短的節點E，將其添加到已訪問的集合中。

11. 將節點E的距離更新周圍可到達節點的距離，節點J的距離為20，節點F的距離為14。

12. 從距離矩陣中選擇距離最短的節點F，將其添加到已訪問的集合中。

13. 將節點F的距離更新周圍可到達節點的距離，節點J的距離為17。

14. 從距離矩陣中選擇距離最短的節點J，將其添加到已訪問的集合中。

15. 所有節點都已經訪問完畢，距離矩陣中顯示了從節點A到所有節點的最短距離，節點J的距離為17，因此，從節點A到節點J的最短路徑是A->D->E->F->J，距離為17。

這就是Dijkstra算法的基本流程，它可以在有向帶權圖中找到最短路徑。注意，如果圖上的邊權重為負數，則此算法可能會出現非最優解。

彙總重點

1. Dijkstra’s Algorithm是一種最短路徑演算法，用於在圖中找到從起始點到終點的最短路徑。

2. 算法需要有一個起點，並通過不斷選擇最短路徑的方式，來進行擴展以找到終點。

3. 在算法開始之前，必須初始化起點到每一個點的距離值為無限大，起始點的距離值為0。

4. 在每個迭代過程中，從未訪問過的點中選擇距離起點最近的一個點作為下一個擴展的節點。

5. 在每個點擴展的過程中，計算更新相鄰節點的距離值，如果該距離值比之前的值更小，則將它更新為新的值。

6. 繼續迭代選擇下一個距離起點最近的未訪問點，直至找到終點或所有點都已訪問。

7. 在算法結束時，通過從終點逆向遍歷每一個節點，可以得到起始點到終點的最短路徑。

知識測驗

1. 給定一個有向帶權圖，求出從指定起點到所有節點的最短路徑。
   答案：Dijkstra演算法可以用來解決這個問題。

2. 給定一個無向帶權圖，求出從指定起點到其它所有節點的最短路徑，每條路徑不能經過特定的邊。
   答案：可以將需要排除的邊權值設為無限大，然後運用Dijkstra演算法求解。

3. 給定一個無向帶權圖，求出從指定起點到終點的最短路徑，其中路徑上最大的權值不能超過指定的值。
   答案：可以使用Dijkstra演算法，但要修改權值比較的方式，要以每個節點到起始節點的距離加上指定路徑權值作為比較標準。

4. 給定一個有向帶權圖和一個權值，求出從指定起點到終點，權值恰好為指定值的路徑。
   答案：可以使用Dijkstra演算法，但要將所有權值小於指定值的邊的權值設為無限大，所有大於指定值的邊的權值也設為無限大。

5. 給定一個無向帶權圖和一個權值K，要求在給定權值範圍內滿足最少邊權值總和的生成樹。
   答案：可以將圖使用Kruskal演算法生成樹後分別使用Dijkstra演算法處理所有生成樹的邊，從而求出最少權值和。