路徑規劃演演算法

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