greedy
時間複雜度O(V*V*V)
Path
(NPC的問題,當沒有負環才是P)
。Shortest path
。Longest path
→利用Dijkstra algo.
Longest path
為 shortest path 的延伸,只要在權重上都上負號 →變成 shortest path 的問題
Shortest path Graph
起點 →終點,形成一張有向圖 →最短路徑圖
每個邊權重皆為正數,最短路徑圖為有向無環圖(DAG)
⭐️Dijkstra Algo
找不在樹上,離根最近的點,每次找訪的點去比較之前最短距離,一直到找到最短路徑為止
→使用時機,有向圖,所有權重皆大於0
如果權重有小於0的 →使用Bellman-Ford Algorithm
EX: 有一Graph如下:
do Dijkstra algo.
。Tabulation