Algorithm - Dijkstra

Course

可以參考我做的課程簡報：

MST & Shortest Path

Dijkstra

單源最短路徑
找離樹根最近的點，加入樹中，並對與該點相連的點鬆弛
也就是，找尋所有於樹上的點 a 中與樹距離最短的點 b
判斷若 dist[b] > dist[a] + w[a][b] 則更新點 b 的 dist[b] 為 dist[a] + w[a][b]

Dijkstra 不可處理負邊

生成步驟

1. 從起點開始推入優先權佇列,尋找與其優先權最大的點 a 連接的點 b
   若 b 原本與根的距離 dist[b] 比從根經過 a 再到 b dist[a] + w[a][b] 還大
2. 更新根到 b 的距離 dist[b] 為 dist[a] + w[a][b]
3. 將點 b 推入優先權佇列

Dijkstra Example

Template

#include<bits/stdc++.h>
using namespace std;

const int maxn = 50000+5;
const int INF = 0x3f3f3f3f;

struct Edge{
    int v, w;
};

struct Item{
    int u, dis;

    // 取路徑最短
    bool operator < (const Item &rhs) const{
        return dis > rhs.dis;
    }
};

vector<Edge> G[maxn];
int dist[maxn];

void Dijkstra(int S){
    memset(dist, INF, sizeof(dist));
    dist[S] = 0;

    priority_queue<Item> pq;
    pq.push({S, 0});

    while(!pq.empty()){
        Item now = pq.top();
        pq.pop();

        // 如果當前走到這個點的路徑比原本走到此點的路徑還長 就不再考慮
        if(now.dis > dist[now.u]) continue;

        // 鬆弛更新
        // 如果有與當前的點相連之點可更新為更短路徑 則將他推入佇列 
        // 讓該點被取出時確認他是否能更新其他與該點相連的點的最短路徑
        for(Edge e : G[now.u]){
            if(dist[e.v] > dist[now.u] + e.w){
                dist[e.v] = dist[now.u] + e.w;
                pq.push({e.v, dist[e.v]});
            }
        }
    }
}

int main(){
    int t, Case = 1;
    cin >> t;

    while(t--){
        int N, M, S, T;
        cin >> N >> M >> S >> T;

        for(int i = 0; i <= N; ++i) G[i].clear();

        int u, v, w;
        for(int i = 0; i < M; ++i){
            cin >> u >> v >> w;

            // 無向圖 所以兩個方向都要推
            G[u].push_back({v, w});
            G[v].push_back({u, w});
        }

        Dijkstra(S);

        cout << "Case #" << Case++ << ": ";
        if(dist[T] == INF) cout << "unreachable" << endl;
        else cout << dist[T] << endl;
    }
}

UVA Problem

UVA 10986 - Sending email