下列那一項演算法（Algorithm）是一種動態規劃（Dynamic Programming）演算法？
AFloyd-Warshall 的全對最短路徑（all-pairs shortest-paths）演算法正確答案
B廣度優先搜索（breadth-first search）演算法
CDijkstra 的單源最短路徑（single-source shortest-paths）演算法
DPrim 的最小生成樹（minimum spanning tree）演算法
答案與詳解
為什麼答案是 A
Floyd-Warshall 以「是否允許經過前 k 個節點」為子問題，透過遞推式 d[i][j]=min(d[i][j], d[i][k]+d[k][j]) 逐步建表，完全符合動態規劃「最佳子結構＋重疊子問題」特性。
考點：DP經典考點：圖走訪考點：貪婪法
載入中…
