最短路徑演算法

習題預習

1. 什麼是Shortest Path Algorithms？該算法如何找到兩點之間的最短路徑？

2. Dijkstra’s Algorithm 與 Bellman-Ford Algorithm 的不同點是什麼？它們如何在實際應用中使用？

3. A* Algorithm 對於搜尋詳細的路徑規劃與運輸系統有何優勢？它是如何運作的？

4. Floyd-Warshall Algorithm 可以處理帶有負權重的圖，但是可能會造成什麼問題？有什麼解決辦法？

5. 在使用Shortest Path Algorithms時，如何評估圖的複雜度？您如何選擇最佳的算法來解決問題？

說明知識

Shortest Path Algorithms 是一種常用的圖論算法，用於在圖論中，找出一個特定起點與終點之間的最短路徑。這種算法主要應用於路徑導航、交通運輸等方面。以下是三種常用的 Shortest Path Algorithms:

1. Dijkstra 算法
   Dijkstra 算法是一種貪心算法，通過選擇當前節點到起始節點距離最短的節點，來逐步構造最短路徑。它的時間複雜度與圖中邊的數量有關，通常為 $O(|E| + |V|\log|V|)$。

舉例：在一張地圖中，我們需要從 A 點出發，前往 B 點，請問最短路徑是哪條？

通過 Dijkstra 算法，我們可以得到 A - C - D - B 這條路徑，其長度為 10。

2. Bellman-Ford 算法
   Bellman-Ford 算法也是一種動態規划算法，通過對圖中所有邊進行 V - 1 次鬆弛操作，來找到最短路徑。它的時間複雜度為 $O(|V||E|)$。

舉例：在一張地圖中，我們需要從 A 點出發，前往 B 點，請問最短路徑是哪條？

通過 Bellman-Ford 算法，我們可以得到 A - C - B 這條路徑，其長度為 6。

3. Floyd-Warshall 算法
   Floyd-Warshall 算法是一種動態規划算法，用於解決所有節點之間的最短路徑問題。它的時間複雜度為 $O(|V|^3)$。

舉例：在一張地圖中，我們需要找到所有節點之間的最短路徑。

通過 Floyd-Warshall 算法，我們可以得到下面的最短路徑矩陣：

0 3 8 1
INF 0 INF 2
INF 4 0 INF
INF INF 5 0

其中，INF 表示無限大。例如，第一列中的數字 0，3，8，1 分別表示從 A 點到 A 點的距離為 0，A 點到 B 點的距離為 3，以此類推。

彙總重點

1. 最短路徑算法是一種計算最短路徑的演算法。
2. Dijkstra算法是一種貪心算法，用於計算無向加權圖中的最短路徑。
3. Bellman-Ford算法是一種動態規划算法，用於計算有向加權圖中的最短路徑。
4. Floyd-Warshall算法是一種動態規划算法，用於計算有向加權圖中的所有頂點對之間的最短路徑。
5. A*算法是一種啟髮式算法，用於計算帶權有向圖中的最短路徑。它使用了估計函數來幫助找到最短路徑。
6. 最短路徑算法可應用於許多問題中，例如交通路網、電信網路、排程等。

知識測驗

1. 在一個帶權有向圖中，從給定源節點到達所有其他節點的最短路徑問題被稱為什麼？

答案：單源最短路徑問題

2. 在Dijkstra算法中，當我們更新某個節點的最短距離，我們還需要更新什麼？

答案：我們同樣需要更新它所有的鄰居節點的最短距離

3. 若在一個帶權有向圖中，從源節點到終點的所有最短路徑都具有相同權值，我們稱該圖為什麼？

答案：單一權重最短路徑問題

4. 在Floyd-Warshall算法中，什麼條件下我們會更新兩個節點之間的最短路徑？

答案：當透過其他節點前往這兩個節點的路徑比直接從源節點到達這兩個節點的路徑更短時，我們可以更新這條路徑

5. 當有負權邊存在於一個圖中，Bellman-Ford算法還能夠確定最短路徑嗎？

答案：是的，Bellman-Ford算法依然能夠確定最短路徑，但需要增加一個檢測負權環的步驟，以避免出現無限循環。