Dijkstra核心: 松弛 + 贪心

算法步骤：

    a. 初始化 dist[1] = 0, dist[i] = +inf  S:当前已经确定为最短距离的点
    b. for(int i = 1; i <= n; i ++)
        {
            1. 寻找不在 S 中距离源点最近的点 t
            2. 将 t 加到 S 中
            3. 用 t 更新其他点的距离(dist[j] = min(dist[j], dist[t] + g[t][j]))
        }

Dijkstra的正确性证明

定理: 最短路径的子路径仍然是最短路径(反证易得)
Dijkstra算法正确性证明: (rel是真实最短距离)
    定理: Dijkstra算法中, 将顶点 u 添加到 S = {1,...,x} 中时,  dist[u] = rel[u] 
       证: 假设 Dijkstra 算法, 将顶点 u 添加到 S 中时,  dist[u] != rel[u]
           由于 dist[u] 是 rel[u] 的上界, 故 dist[u] > rel[u]

           应存在一条真实的最短路径 rel[u], 不妨设其为<1,...,x,y,...,u>,
           其中边 (x, y) 横跨 <S, V-S>, x 属于 S, y 属于 V-S
           对任意 x 属于 S, 有 rel[x] = dist[x]

           1.<1,...,x,y>是<1,...,x,y,...,u>的子路径, 故:
                rel[y] = rel[x] + w[x][y] = dist[x] + w[x][y]

           2.算法对从 x 出发的所有边进行松弛操作, 故:
                dist[y] <= dist[x] + w[x][y]
           由于 dist 是 rel 的上界, 于是综合 1 与 2 可得 dist[y] = rel[y]

           最短路径<1,...,x,y,...,u>中, y 出现在 u 之前, 故:
           dist[u] > rel[u] >= rel[y] > dist[y]
           由于 dist[u] > dist[y], u 不可能是下一个被添加的顶点, 故产生矛盾

算法1

朴素Dijkstra算法(适用于稠密图)

时间复杂度

    1. 寻找路径最短的点：O(n^2)
    2. 加入集合S：O(n)
    3. 更新距离：O(m)
       总时间复杂度为O(n^2)

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;

const int N = 510;

int n, m;
int g[N][N];
int d[N];
bool st[N];

void dijkstra() {
    memset(d, 0x3f, sizeof d);
    d[1] = 0;

    for (int i = 0; i < n - 1; i ++) {
        int t = -1;
        for (int i = 1; i <= n; i ++) 
            if (!st[i] && (t == -1 || d[t] > d[i])) t = i;

        st[t] = true;

        for (int i = 1; i <= n; i ++)
            d[i] = min(d[i], d[t] + g[t][i]);
    }

    if (d[n] == 0x3f3f3f3f) puts("-1");
    else printf("%d", d[n]);
}

int main() {
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);//初始化邻接矩阵每个元素为 +inf
    for (int i = 0; i < m; i ++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = min(c, g[a][b]);
    }

    dijkstra();

    return 0;
}

算法2

堆优化版的Dijkstra算法(适用于稀疏图)

时间复杂度

    显然朴素Dijkstra最大开销在寻找最短路径, 于是利用优先队列进行改进
        1. 寻找路径最短的点：O(nlogn)(最小值+出队)
        2. 加入集合S：O(n)
        3. 更新距离：O(mlogn)(采用c++中优先队列直接加边即可, 同样也是 mlogn 级别)
    总时间复杂度为O(mlogn)

C++ 代码

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

typedef pair<int, int> PII;

const int N = 2e5;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
bool st[N];
int d[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

void dijkstra() {
    memset(d, 0x3f, sizeof d);
    d[1] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({d[1], 1});

    while (q.size()) {
        auto t = q.top();
        q.pop();

        int vex = t.second;
        if (st[vex]) continue;//访问过不再访问
        st[vex] = true;//标记

        for (int i = h[vex]; i != -1; i = ne[i]) {// i 指向 vex 的某个邻接点
            int j = e[i];
            if (d[j] > d[vex] + w[i]){// w[i] 表示边 (vex, j) 的长度
                d[j] = d[vex] + w[i];
                q.push({d[j], j});
            }
        }
    }

    if (d[n] == 0x3f3f3f3f) puts("-1");
    else printf("%d", d[n]);

}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);

    for (int i = 0; i < m; i ++){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    dijkstra();

    return 0;
}