國營事業◆1.計算機原理 2.網路概論題庫下載題庫

Dijkstra 演算法 在某些情況下可被視為具有動態規劃的特徵，特別是在其以矩陣形式求解最短路徑時，可以視作使用了重疊子問題的思想。

動態規劃（Dynamic Programming，簡稱 DP）是一種通過將問題分解成子問題並重複利用子問題的解來解決複雜問題的技術。動態規劃演算法的分類主要是根據解決問題的方式、子問題的性質和應用場景來劃分的。

 

Fibonacci 數列或一些遞迴問題就是很經典的動態規劃

 

而 Dijkstra 是Greedy Algorithm，就如果A/B一樣，但它在更新最短路徑的過程中，實際上也有一種基於先前狀態去計算下一個答案的意味，跟遞歸有點類似。

 

舉例來說，Dijkstra到最後的算式大概如下

• A 到 B 的最短路徑：A -> B，距離為 2
• A 到 C 的最短路徑：A -> C，距離為 1
• A 到 D 的最短路徑：A -> D，距離為 3
• A 到 E 的最短路徑：A -> C -> E，距離為 7
• A 到 F 的最短路徑：A -> B -> F，距離為 3