Dijkstra Algorithm
- 兩個頂點之間的最短路徑
- 不能有效處理帶有負權邊的圖(使用 Bellman-Ford 算法)
- 演算法概念與流程:
- 一張表格紀錄以下內容 - 點到點的距離、前一個點(回推得知最短路徑)、是否已經存取過節點(Boolean)
- 距離欄位,與自己本身指定為 0、其餘設定為 Infinity
- 每次從未標記已存取的節點中,選擇與起點距離最短的節點,標記後收錄到最優路徑集合中
- 計算剛標記的節點與鄰近節點距離,當前距離 < 先前距離,則更新距離欄位與前一個點。反之,則不更新。
