Dijkstra演算法原理詳解

語言: CN / TW / HK

開啟掘金成長之旅!這是我參與「掘金日新計劃 · 12 月更文挑戰」的第2天,點選檢視活動詳情

演算法簡介

  1. Dijkstra演算法是求點到點之間的最短路徑演算法。
  2. 它是一種廣度優先搜尋演算法。
  3. 它採用的是一種貪心思想策略。
  4. 基於搜尋的一種演算法。

Dijkstra演算法是最基礎的路徑規劃演算法之一,廣泛應用於移動機器人的全域性路徑規劃中。對於研究路徑規劃方向的人而言,它是必須要了解要學會的。下面來探索一下,Dijkstra演算法的原理及實現流程。

實現原理

image.png

如圖,可以知道每個節點以及各節點之間的權重關係,聯絡到實際應用場景,這個權重關係就是每個柵格點的距離。下面介紹Dijkstra演算法是怎樣實現的。

第一步:新增起始點,然後新增進已標記列表,表明該點已經被處理過了,後續不再處理這個點了。 第二步:然後根據0號節點,找到相關的1號節點和7號節點。將距離值填入表中,未處理到的點標記為∞。併為1號點和7號點標記上一個節點。

| 節點序號 | 距離 | 上一個節點 | 是否新增 | | -------- | ---- | ---------- | -------- | | 0 | 0 | |√ | | 1 | 4 | 0 | | | 2 | ∞ | | | | 3 | ∞ | | | | 4 | ∞ | | | | 5 | ∞ | | | | 6 | ∞ | | | | 7 | 7 | 0 | | | 8 | ∞ | | |

第三步:從第二步的結果中找到距離最短的一個節點,作為新的起始點,這裡面距離最短的是1號節點,距離為4,將這個1號節點標記,並找到與1號節點相關的節點,2號節點和7號節點,1號節點本身的距離是4,加上距離2號節點的距離為8,故2號節點的距離是12,記下2號節點的上一個節點是1。由於1號節點距離7號節點的距離是11,加上1號節點本身距離4,故0-1-7的距離是15,大於0-7的距離為8,故不再更新7號節點的距離。

| 節點序號 | 距離 | 上一個節點 | 是否新增 | | -------- | ---- | ---------- | -------- | | 0 | 0 | |√ | 1 | 4 | 0 |√ | 2 | 12 | 1 | | 3 | ∞ | | | 4 | ∞ | | | 5 | ∞ | | | 6 | ∞ | | | 7 | 7 | 0 | | 8 | ∞ | |

第四步:在第三步的基礎上,繼續找距離最短的節點,這裡面已經找過的點是0號,1號點,剩下的點中距離最短的是7號點,距離為7。依次類推,找到7的相關節點,並更新與之相關節點的距離,和上一個節點標號。 | 節點序號 | 距離 | 上一個節點 | 是否新增 | | -------- | ---- | ---------- | -------- | | 0 | 0 | |√ | 1 | 4 | 0 |√ | 2 | 12 | 1 | | 3 | ∞ | | | 4 | ∞ | | | 5 | ∞ | | | 6 | 9 | 7 | | 7 | 7 | 0 |√ | 8 | 15 | 7 |

| 節點序號 | 距離 | 上一個節點 | 是否新增 | | -------- | ---- | ---------- | -------- | | 0 | 0 | |√ | 1 | 4 | 0 |√ | 2 | 12 | 1 | | 3 | ∞ | | | 4 | ∞ | | | 5 | 11 | 6 | | 6 | 9 | 7 |√ | 7 | 7 | 0 |√ | 8 | 15 | 7 |

| 節點序號 | 距離 | 上一個節點 | 是否新增 | | -------- | ---- | ---------- | -------- | | 0 | 0 | |√ | 1 | 4 | 0 |√ | 2 | 12 | 1 | | 3 | 25 | 5 | | 4 | 21 | 5 | | 5 | 11 | 6 |√ | 6 | 9 | 7 |√ | 7 | 7 | 0 |√ | 8 | 15 | 7 |

| 節點序號 | 距離 | 上一個節點 | 是否新增 | | -------- | ---- | ---------- | -------- | | 0 | 0 | |√ | 1 | 4 | 0 |√ | 2 | 12 | 1 |√ | 3 | 19 | 2 | | 4 | 21 | 5 | | 5 | 11 | 6 |√ | 6 | 9 | 7 |√ | 7 | 7 | 0 |√ | 8 | 14 | 2 |

| 節點序號 | 距離 | 上一個節點 | 是否新增 | | -------- | ---- | ---------- | -------- | | 0 | 0 | |√ | 1 | 4 | 0 |√ | 2 | 12 | 1 |√ | 3 | 19 | 2 | | 4 | 21 | 5 | | 5 | 11 | 6 |√ | 6 | 9 | 7 |√ | 7 | 7 | 0 |√ | 8 | 14 | 2 |√

經過多次迴圈遍歷,將所有的點遍歷完成。或者,遍歷到目標終點即可結束。 可以得到每一個節點的最短距離,以及上一個節點編號。

| 節點序號 | 距離 | 上一個節點 | 是否新增 | | -------- | ---- | ---------- | -------- | | 0 | 0 | |√ | 1 | 4 | 0 |√ | 2 | 12 | 1 |√ | 3 | 19 | 2 |√ | 4 | 21 | 5 | | 5 | 11 | 6 |√ | 6 | 9 | 7 |√ | 7 | 7 | 0 |√ | 8 | 14 | 2 |√

例如:想找到起點0到終點4的最短路徑,根據表格可得,路徑為0->7->6->5->4,最短距離為21。(倒推法,4上一個節點是5,5上一個節點是6。。。依次類推)

程式設計實現

```cpp

include

include

using namespace std; // this method returns a minimum distance for the // vertex which is not included in Tset. int minimumDist(int dist[], bool Tset[]) { int min = INT_MAX, index;

for (int i = 0; i < 6; i++)
{
    if (Tset[i] == false && dist[i] <= min)
    {
        min = dist[i];
        index = i;
    }
}
return index;

} void Dijkstra(int graph[6][6], int src) // adjacency matrix used is 6x6 { int dist[6]; // integer array to calculate minimum distance for each node.
bool Tset[6];// boolean array to mark visted/unvisted for each node.

// set the nodes with infinity distance
// except for the initial node and mark
// them unvisited.  
for (int i = 0; i < 6; i++)
{
    dist[i] = INT_MAX;
    Tset[i] = false;
}

dist[src] = 0;   // Source vertex distance is set to zero.

for (int i = 0; i < 6; i++)
{
    int m = minimumDist(dist, Tset); // vertex not yet included.
    Tset[m] = true;// m with minimum distance included in Tset.
    for (int i = 0; i < 6; i++)
    {
        // Updating the minimum distance for the particular node.
        if (!Tset[i] && graph[m][i] && dist[m] != INT_MAX && dist[m] + graph[m][i] < dist[i])
            dist[i] = dist[m] + graph[m][i];
    }
}
cout << "Vertex\t\tDistance from source" << endl;
for (int i = 0; i < 6; i++)
{ //Printing
    char str = 65 + i; // Ascii values for pritning A,B,C..
    cout << str << "\t\t\t" << dist[i] << endl;
}

} int main() { int graph[6][6] = { {0, 10, 20, 0, 0, 0}, {10, 0, 0, 50, 10, 0}, {20, 0, 0, 20, 33, 0}, {0, 50, 20, 0, 20, 2}, {0, 10, 33, 20, 0, 1}, {0, 0, 0, 2, 1, 0} }; Dijkstra(graph, 0); return 0; } ```

output: bash Vertex Distance from source A 0 B 10 C 20 D 23 E 20 F 21

理論分析:

image.png

| 節點 | 距離 | 上一個節點 | mark | |:----:|:----:|:----------:|:----:| | A | 0 | | √ | | B | 10 | A | √ | | C | 20 | A | √ | | D | 23 | F | √ | | E | 20 | B | √ | | F | 21 | E | √ |

例如從A到D點最短路徑為:A->B->E->F->D,最短距離為23。