演算法知識 - Dijkstra's Algorithm (無權重、有權重向圖)

Dijkstra’a Algorithm 介紹

能夠針對有、無權重的有向圖做出單點全源最短路徑演算法。

• 單點全源：從 A 點到任意邊的最短距離
  時間複雜度為 \(O((E+V)log V)\)，E 為邊、V 為頂點

Dijkstra’s Algorithm 證明與實作

證明

• 我們知道無權重的有向圖可以做出單點全源最短路徑演算法。keyword: spfa
• 但是如果有權重的時候有可能 queue 上面的節點並不是最快速的節點，因為放入 queue 的順序是依照時間放入。
• 因此我們改使用 priority_queue 將 queue 的排序從依照時間放入更改為queue 中成本最小的值。
• 理所當然，成本最小的值加上任一相同路徑也還會是最小
  • EX: \(3+5 =8, 10+5 = 15\)
• 其他與無權重的有向圖相同。

原理

• 使用 priority_queue，內部資料結構為 (root, cost)
• 放入節點 (root,0)，root 為出發點節、0 表示成本
• 進行 BFS，並用一陣列從出發點到 x 點最短距離。
  • 其中 E 表示有一條邊從 root 到 x
  • 如果 \((root, cost) + E(root,x).成本 > 當前 x 點最短距離 \)
    • \( 當前 x 點最短距離 = (root, cost) + E(root,x).成本 \)
    • priority_queue.push(x, 當前 x 點最短距離)

Dijkstra Algorithm 實作

不廢話，直接上來

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
#define MAXN 10020
#define INF 2100000000
using namespace std;
struct Edge{ // 我們使用 Edge struct 實做 (root, cost)
    int v, c;
    Edge(): v(0), c(0) {}
    Edge(int _v, int _c): v(_v), c(_c) {}
};

struct Status{ // 我們使用 Status struct 實做 priority_queue (root, cost)
    int v, c; //v 節點, c 成本
    Status(): v(0), c(0) {}
    Status(int _v, int _c): v(_v), c(_c) {}

    bool operator < (const Status& other) const{ 
        return c < other.c; //遞減排序，決定 priority_queue 的方式
        //return c > other.c; //遞增排序
    }
};

int c, v;
int a, b, cost;
vector<Edge> edge[MAXN]; //放入題目的邊
int dist[MAXN]; //從 root 出發到 x 邊的最短距離

void dijkstra(int root){
    priority_queue<Status> q;
    q.push({root,0}); //初始放入開始點
    dist[root] = 0; //自己到自己成本為零

    int cost;
    while(!q.empty()){
        Status node = q.top(); q.pop(); 
        //cout << node.v << " " << node.c << "\n";
        for(auto it: edge[node.v]){
            cost = dist[node.v] + it.c; //分析 3
            if(cost < dist[it.v]){ 
                q.push({it.v, cost});
                dist[it.v] = cost;
            }
        }
    }
}


int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    while(cin >> c >> v){
        for(int i = 1; i <= c; i++){ //清除邊、重置距離
            edge[i].clear();
            dist[i] = INF; 
            dist[i] = -INF; //當題目要求，是最大成本時使用
        }
        for(int i = 0; i < v; i++){ //加入邊
            cin >> a >> b >> cost;
            edge[a].push_back({b,cost}); //單向時使用
            edge[b].push_back({a,cost}); //雙向時使用
        }
        dijkstra(root); //root 為任移值，為開始的點
        if(dist[x] == INF) cout << "-1\n"; // root -> x 最短距離為多少，無法抵達輸出 -1
        else cout << dist[x] << "\n"; //可以抵達則輸出。
    }
    return 0;
}