背景

今天基本上刷了所有的最短路径算法了，从之前无权重的BFS，然后是图论里的最短路径算法。acwing上总结了5种算法的用法，如下图：

这篇文章主要是还是总结下各种算法的用法，加强自己的记忆。

朴素dijkstra算法O(n ^ 2)，适合稠密图
朴素dijkstra算法的思路是，初始化距离d[1] = 0, 其余为正无穷INF。
循环n - 次，从当前距离数组中选出距离最短且没有遍历过的节点i，并用该节点的出边w更新其余的邻接点j的距离，d[j] = min(d[j], d[i] + w)
最后d[n]就是1号节点到所有节点的最短路径。 ```cpp
include
include
using namespace std;

define N 510

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

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

for (int i = 0; i < n; i ++) {
    int t = -1;
    for (int j = 1; j <= n; j ++) {
        if (st[j]) {
            continue;
        }
        if (t == -1 || dist[j] < dist[t]) {
            t = j;
        }
    }
    // cout << t << " " << dist[t] << endl;
    st[t] = true;
    for (int j = 1; j <= n; j ++) {
        dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
}

}

int main() { scanf(“%d%d”, &n, &m); memset(g, 0x3f, sizeof g);

while(m --) {
    int a, b, d;
    scanf("%d%d%d", &a, &b, &d);
    g[a][b] = min(g[a][b], d);
}

dijkstra();

if (dist[n] == 0x3f3f3f3f) {
    cout << -1 << endl;
} else {
    cout << dist[n] << endl;
}
return 0;

}

<a name="J3R57"></a>
#### 堆优化的dijkstra算法O(m logn)，适合稀疏图

- 相比朴素dijkstra算法，堆优化的算法是通过堆存放距离，并且可以logm的复杂度获取对应的最短距离。
- 其余保持不变
```cpp
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

#define M 150010
int dist[M], h[M];
bool st[M];
int e[M], ne[M], w[M], idx;
int n, m;
typedef pair<int, int> PII;

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

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof(h));
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    while(m --) {
        int a, b, d;
        scanf("%d%d%d", &a, &b, &d);
        add(a, b, d);
    }
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    // first represent distance
    // second represent node idx
    heap.push({0, 1});

    while(heap.size()) {
        auto t = heap.top();
        heap.pop();
        if (st[t.second]) {
            continue;
        }
        st[t.second] = true;
        for (int i = h[t.second]; i != -1; i = ne[i]) {
            if (dist[e[i]] > dist[t.second] + w[i]) {
                dist[e[i]] = dist[t.second] + w[i];
                heap.push({dist[e[i]], e[i]});
            }
        }
    }
    if (dist[n] == 0x3f3f3f3f) {
        cout << -1 << endl;
    } else {
        cout << dist[n] << endl;
    }
    return 0;
}

bellman-ford算法O(nm)

bellman-ford算法的思路是，循环n次，每次更新都遍历所有的边，看哪些距离可以更新，能更新的就更新下。循环n次后，d[n]就是1号节点到所有节点的最短路径。
bellman-ford算法的循环次数的实际含义是，经过k条边的最短路径。
根据循环次数的定义，该次循环只需要更新加一条边后对应的距离，backup数组是为了防止连续更新。 ```cpp
include
include
using namespace std;

const int N = 510, M = 10010; struct Edge { int a, b, w; } edge[M]; int n, m, k; int dist[N], back_dist[N];

void bellman_ford() { memset(dist, 0x3f, sizeof(dist)); dist[1] = 0;

for (int i = 0; i < k; i ++) {
    memcpy(back_dist, dist, sizeof(dist));

    for (int j = 0; j < m; j ++) {
        int a = edge[j].a, b = edge[j].b, w = edge[j].w;
        dist[b] = min(dist[b], back_dist[a] + w);
    }
}

}

int main() {

scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < m; i ++) {
    scanf("%d%d%d", &edge[i].a, &edge[i].b, &edge[i].w);
}

bellman_ford();

if (dist[n] > 0x3f3f3f3f / 2) {
    puts("impossible");
} else {
    cout << dist[n] << endl;
}
return 0;

}

<a name="KDvku"></a>
#### spfa算法O(m)，最坏O(nm)

- 其实根据dijkstra算法可以知道，更新距离的时候并不需要查看所有的边。
- 更新边的必要条件是前一个节点的的距离更新了，所以可以维护一个节点距离更新的队列，每个节点距离更新后就放在队列中，然后每次拿一个节点来更新邻接点的距离。
- 队列空的时候d[n]就是1号节点到所有节点的最短路径。
- st数组标识是否在队列中，防止重复更新
```cpp
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

#define N 100010
int h[N], e[N], ne[N], w[N], dist[N];
bool st[N];
int idx, n, m;

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

void spfa()
{
    memset(dist, 0x3f, sizeof dist);
    queue<int> q;
    dist[1] = 0;
    q.push(1);
    st[1] = true;

    while(q.size()) {
        int t = q.front();
        q.pop();
        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i ++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    spfa();
    if (dist[n] == 0x3f3f3f3f) {
        cout << "impossible" << endl;
    } else {
        cout << dist[n] << endl;
    }
    return 0;
}

Floyd算法

三层循环，用邻接矩阵计算各个点到某个点的最短距离。
floyd是基于动态规划的思想，只经过前[1-k]的最短距离 ```cpp
include
using namespace std;

const int N = 210, M = 20010, INF = 0x3f3f3f3f; int d[N][N]; int n, m, k;

void floyd() { for (int k = 1; k <= n; k ++) { for (int i = 1; i <= n; i ++) { for (int j = 1; j <= n; j ++) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } }

int main() { scanf(“%d%d%d”, &n, &m, &k); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j ++) { if (i == j) { d[i][j] = 0; } else { d[i][j] = INF; } } }

while(m --) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    d[a][b] = min(d[a][b], c);
}

floyd();

while(k --) {
    int a, b;
    scanf("%d%d", &a, &b);
    if (d[a][b] > INF / 2) {
        cout << "impossible" << endl;
    } else {
        cout << d[a][b] << endl;
    }
}
return 0;

} ```

最短路径算法

背景

朴素dijkstra算法O(n ^ 2)，适合稠密图

include

include

define N 510

bellman-ford算法O(nm)

include

include

Floyd算法

include