淺談Dijkstra演算法

何謂Dijkstra Algorithm

Dijkstra Algorithm(戴克斯特拉演算法) 是由荷蘭電腦學家Edsger Wybe Dijkstra 於1956年所發現的演算法。Dijkstra演算法用於尋找一張圖(Graph)任兩個節點(Nodes/Vertexes)之間的最短路徑。

常見應用：

• GPS
• Network Routing
• Biology：通常用來示範人體中的細菌分佈
• Airline tickets：找出最便宜的機票路線

source: JavaScript Algorithms and Data Structures Masterclass

鬆弛(Relax)

鬆弛是Dijkstra演算法的精隨所在。 以下圖為例，若從節點$1$ 直接走到節點$4$ 總共需要$7$個單位長。但從節點$1$ 經過節點$2$ 再走到節點$4$，總共只需$5$個單位長。後者明顯路徑較短，此時我們會稱節點$2$ 鬆弛了節點$1$到節點$4$。 我們就是透過這個不斷鬆弛的原理，來理解Dijkstra Algorithm。

算法原理

以上方的動畫為例子，假設節點1為起點，節點5為終點 關鍵假設：所有節點(除起點)到起點目前的最短距離設為無限大，起點到起點的最短距離一開始為0

1. 先走過節點1的相鄰節點(2&3&4)，鬆弛後，距離分別更新為1、4、2
2. 未遍歷過且目前距起點距離最短的節點2為我們下個討論的對象。走過節點2的相鄰節點(3)，因目前節點3離起點的距離小於經過2再到3的距離，所以鬆弛失敗，不更新距離
3. 未遍歷過且目前距起點距離最短的節點4為我們下個討論的對象。走過節點4的相鄰節點(3&5)，節點3鬆弛失敗；節點5鬆弛後距離更新為7
4. 未遍歷過且目前距起點距離最短的節點3為我們下個討論的對象。走過節點4的相鄰節點(5)，節點5鬆弛後距離更新為5
5. 未遍歷過且目前距起點距離最短的節點5為我們下個討論的對象。節點5已無相鄰節點，且所有節點皆遍歷過了。
6. 取得結果：節點1到節點5之最短距離為5

程式碼實現Dijkstra Algorithm(C++)

#define pii pair<int,int>
#define F first
#define S second
int dis[MAXN], vis[MAXN]; //dis存距離 vis紀錄是否拜訪過
vector <pii> gra[MAXN]; //存圖
priority_queue<pii,vector<pii>,greater<pii>> pq;
//排優先造訪順序(先由路徑小開始)

void dijkstra(int n){
    if (vis[n]){
        pq.pop();
        if (!pq.empty()) dijkstra(pq.top().S);
        return;
    }
    vis[n]=1;
    for (pii i:gra[n]){
        if (vis[i.F]) continue; //不重複拜訪
        if (dis[i.F]>dis[n]+i.S){ //鬆弛成功
            dis[i.F]=dis[n]+i.S; //更新距離
            pq.push({dis[i.F],i.F});
        }
    }
    if (!pq.empty()) dijkstra(pq.top().S);
    return;
}

//距離一開始設為無限大(INT_MAX)，起點的距離設為0

參考資料

基礎演算法系列 — Graph 資料結構與Dijkstra’s Algorithm [演算法] 學習筆記 — 14. Dijkstra Algorithm 最短路徑演算法 Graph Data Structure 4. Dijkstra’s Shortest Path Algorithm