技術文章 » 路徑規劃演演算法

路徑規劃演演算法

2023-12-07 12:06:45

Dijkstra(迪傑斯特拉)演演算法的思想是廣度優先搜尋（BFS） 貪心策略。
是從一個頂點到其餘各頂點的最短路徑演演算法，節點邊是不各自不同的權重，但都必須是正數
如果是負數，則需要 Bellman-Ford 演演算法
如果想求任意兩點之間的距離，就需要用 Floyd 演演算法

求節點0 -> 4 的最短路徑

  • 每次從未標記的節點中選擇距離出發點最近的節點，標記，收錄到最優路徑集合中
  • 計算剛加入節點A的鄰近節點B的距離（不包括標記的節點），若（節點A的距離 + 節點A到節點B的邊長）< 節點B的距離，就更新節點B的距離和前序節點

初始狀態

節點 0 1 2 3 4 5 6 7 8 備註
最優節點 每一步，找出未標記的節點中，最短的距離，標記為最優節點
出發節點 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 當前節點，到每個節點的距離，剛開始，所有的節點都認為是 ∞ 無窮大
前序點 為了記錄最短路徑，需要記錄每個節點的前序節點

從0出發

節點 0 1 2 3 4 5 6 7 8
最優節點 ✔️
0 出發 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
前序點

首先，節點0的距離是0，所有節點中距離最短的是它自己，0為最優路徑中的節點

更新0鄰近節點1、7

從0點出發，到 相鄰的節點 1、7
0->1 = 4 , 節點 1 此時為 ∞，因此 節點 1 的 距離 標為 4，前序節點為 0
0->7 = 8 , 節點 7 此時為 ∞，因此 節點 7 的 距離 標為 8，前序節點為 0

從未標記最優節點（1~8）中，找距離出發點最小的節點 => 1

節點 0 1 2 3 4 5 6 7 8
最優節點 ✅ ✔️
0 出發 0 4 ∞ ∞ ∞ ∞ ∞ 8 ∞
前序點 0 0

更新1鄰近節點2、7

上一次的最優節點是 1

從0點出發，到 節點 1 相鄰的節點 2、7
0->1->2 = 4 + 8 = 12 , 節點 2 此時為 ∞，因此 節點 2 的 距離 標為 12，前序節點為 1
0->1->7 = 4 + 11 = 15 , 節點 7 已有值 8，8<15，因此 節點7 的 距離、前序節點保持不變
從未標記最優節點（2~8）中，找距離出發點最小的節點 => 7

節點 0 1 2 3 4 5 6 7 8
最優節點 ✅ ✅ ✔️
0 出發 0 4 12 ∞ ∞ ∞ ∞ 8 ∞
前序點 0 1 0

更新7鄰近節點 8、6

上一次的最優節點是 7

從0點出發，到 節點 7 相鄰的節點 8、6
0->7->8 = 8 + 7 = 15 , 節點 8 此時為 ∞，因此 節點 8 的 距離 標為 15，前序節點為 7
0->7->6 = 8 + 1 = 9 , 節點 6 此時為 ∞，因此 節點 6 的 距離 標為 9，前序節點為 7
從未標記最優節點（2~6、8）中，找距離出發點最小的節點 => 6

節點 0 1 2 3 4 5 6 7 8
最優節點 ✅ ✅ ✔️ ✅
0 出發 0 4 12 ∞ ∞ ∞ 9 8 15
前序點 0 1 7 0 7

更新6鄰近節點 8、5

上一次的最優節點是 6

從0點出發，到 節點 6 相鄰的節點 8、5
0->7->6->8 = 8 + 1 + 6 = 15 , 節點 8 已有值 15，15=15，因此 節點 8 的 距離、前序節點保持不變
0->7->6->5 = 8 + 1 + 2 = 11 , 節點 5 此時為 ∞，因此 節點 5 的 距離 標為 11，前序節點為 6
從未標記最優節點（2~5、8）中，找距離出發點最小的節點 => 5

節點 0 1 2 3 4 5 6 7 8
最優節點 ✅ ✅ ✔️ ✅ ✅
0 出發 0 4 12 ∞ ∞ 11 9 8 15
前序點 0 1 6 7 0 7

更新5鄰近節點 2、3、4

上一次的最優節點是 5

從0點出發，到 節點 5 相鄰的節點 2、3、4
0->7->6->5->2 = 8 + 1 + 2 + 4 = 15 , 節點 2 已有值 12，12<15，因此 節點2 的 距離、前序節點保持不變
0->7->6->5->3 = 8 + 1 + 2 + 14 = 25 , 節點 3 此時為 ∞，因此 節點 3 的 距離 標為 25，前序節點為 5
0->7->6->5->4 = 8 + 1 + 2 + 10 = 21 , 節點 4 此時為 ∞，因此 節點 4 的 距離 標為 21，前序節點為 5
從未標記最優節點（2、3、4、8）中，找距離出發點最小的節點 => 2

節點 0 1 2 3 4 5 6 7 8
最優節點 ✅ ✅ ✔️ ✅ ✅ ✅
0 出發 0 4 12 25 21 11 9 8 15
前序點 0 1 5 5 6 7 0 7

更新2鄰近節點 3、8

上一次的最優節點是 2

從0點出發，到 節點 2 相鄰的節點 3、5、8，節點5已標記，所以不處理節點5
0->1->2->3 = 4 + 8 + 7 = 19 , 節點 3 已有值 25，25>19，因此 節點 3 的 距離 標為 19，前序節點為 2
0->1->2->8 = 4 + 8 + 2 = 14 , 節點 8 已有值 15，15>14，因此 節點 8 的 距離 標為 14，前序節點為 2
從未標記最優節點（3、4、8）中，找距離出發點最小的節點 => 8

節點 0 1 2 3 4 5 6 7 8
最優節點 ✅ ✅ ✅ ✅ ✅ ✅ ✔️
0 出發 0 4 12 19 21 11 9 8 14
前序點 0 1 2 5 6 7 0 2

更新8鄰近節點

上一次的最優節點是 8

8的鄰近節點，2、7、6 都已被標記為最優節點，所以不需要處理
從未標記最優節點（3、4）中，找距離出發點最小的節點 => 3

節點 0 1 2 3 4 5 6 7 8
最優節點 ✅ ✅ ✅ ✔️ ✅ ✅ ✅ ✅
0 出發 0 4 12 19 21 11 9 8 14
前序點 0 1 2 5 6 7 0 2

更新3鄰近節點

上一次的最優節點是 3

最優節點3的鄰近節點：2、5、4中 2、5都已被標記為最優節點，處理 4
0->1->2->3->4 = 19 + 9 = 28 , 節點 4 已有值 21，21<28，因此 節點 4 的 距離 、前序節點保持不變
從未標記最優節點（4）中，找距離出發點最小的節點 => 4

節點 0 1 2 3 4 5 6 7 8
最優節點 ✅ ✅ ✅ ✅ ✔️ ✅ ✅ ✅ ✅
0 出發 0 4 12 19 21 11 9 8 14
前序點 0 1 2 5 6 7 0 2

已時已全部結束

最短距離

從出發點0 到節點 4 的最短距離 = 21

最短路徑

反向追溯
4 的前序節點 5，5的前面是 6 ... => 4 -> 5 -> 6 -> 7 -> 0
因此 0 -> 7 -> 6 -> 5 -> 4 是最短路徑

https://www.bilibili.com/video/BV1zz4y1m7Nq