最短路

graph LR
A[最短路] --> B[单源最短路]
A --> C[多源汇最短路]

B --> D[所有边权都是正数]
B --> E[存在负权边]

D --> D1["朴素 Dijkstra 算法 <br/> O(n²)"]
D --> D2["堆优化版的 Dijkstra 算法 <br/> O(m log n)"]

E --> E1["Bellman-Ford <br/> O(nm)"]
E --> E2["SPFA <br/> 一般 O(m), 最坏 O(nm)"]

C --> C1["Floyd 算法 <br/> O(n³)"]

单源最短路

正数边权

朴素Dijkstra（稠密）

https://www.acwing.com/problem/content/851/

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

const int N = 510;
int n, m;
int g[N][N];//存两点间长度
int dist[N];//存1到某点距离
bool st[N];//是否走过

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);//初始化距离
    dist[1] = 0;//标记初始点
    for (int i = 0; i < n; i++)
    {
        int t = -1;//保证t一定会变
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;//找出未标记的最近点

        st[t] = true;//标记走过

        for (int j = 1; j <= n; j++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);//用t更新临近点的最短路
    }
    if (dist[n] == 0x3f3f3f3f)//走不通
        return -1;
    return dist[n];
}

signed main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);//初始化两点距离数组
    while (m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);//两点有多条赋权边，因此保留最短
    }
    int t = dijkstra();
    printf("%d", t);
}

堆优化版Dijkstra

https://www.acwing.com/problem/content/852/

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 150010;
int n, m;
int e[N], w[N], h[N], ne[N], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b;
    w[idx] = c;//赋权边
    ne[idx] = h[a];
    h[a] = idx++;
}//邻接表基操

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist); // 初始化距离
    dist[1] = 0;                     // 标记初始点

    priority_queue<PII, vector<PII>, greater<PII>> heap; // 建堆
    heap.push({0, 1});

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

        int ver = t.second, distance = t.first;
        if (st[ver])
            continue;//确定最短边直接过
        st[ver] = true;
        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});//入堆
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) // 走不通
        return -1;
    return dist[n];
}

signed main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while (m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c); // 建边
    }
    int t = dijkstra();
    printf("%d", t);
}

存在负权边

bellman-ford

https://www.acwing.com/activity/content/problem/content/922/

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 510, M = 10010;
int n, m, k;
int dist[N], backup[N];

struct edge
{
    int a, b, w;
} edge[M];

int bellman()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < k; i++)
    {
        memcpy(backup, 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], backup[a] + w);
        }
    }
    return dist[n];
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;
    for (int i = 0; i < m; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        edge[i] = {a, b, w};
    }
    int t = bellman();
    if (t > 0x3f3f3f3f / 2)
        puts("impossible");
    else
        cout << t << endl;
}

sofa(bellman-ford优化)

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m;
int e[N], w[N], h[N], ne[N], idx;
int dist[N];
bool st[N];

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

int spfa()
{
    memset(dist, 0x3f, sizeof dist); // 初始化距离
    dist[1] = 0;                     // 标记初始点

    queue<int> q;
    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;
                }
            }
        }
    }

    return dist[n];
}

signed main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while (m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c); // 建边
    }
    int t = spfa();
    if (t == 0x3f3f3f3f)
        puts("impossible");
    else
        cout << t << endl;
}

spfa在思路上是belman-ford优化，但是代码上更接近堆优化Dijkstra

Q：为什么如果 j 已经在队列里，就没必要重复放。否则队列里会有很多重复点，效率变差

A：比如一个点 j 已经在队列里等着被处理了，这时又有别的点把 dist[j] 更新得更小，如果不判断 st[j]，就会再把 j 放进去一次，于是队列里就有重复的 j。

举个图：

1 -> 2 权重 10
1 -> 3 权重 1
3 -> 2 权重 1

起点是 1。

初始化：

queue: 1
dist[1] = 0

取出 1，它能更新：

dist[2] = 10
dist[3] = 1

于是把 2 和 3 放进队列：

queue: 2, 3

这时 2 已经在队列里了。

然后取出 3，发现：

3 -> 2 权重 1

可以把：

dist[2] = 10

更新成：

dist[2] = dist[3] + 1 = 2

此时 2 的距离变短了。

如果没有这个判断：

if (!st[2])

那就又会执行：

q.push(2);

队列会变成：

queue: 2, 2

这就是重复点。

spfa求负环

基于最短路代码改几处即可

1. 新建cnt数组用于存图
2. 不需要初始化，因为不是求最短路绝对值关键是cnt
3. 将所有点初始入队防止最短路不需要路过负环导致遗漏

多源汇最短路

Floyd

#include <bits/stdc++.h>
using namespace std;
const int N = 210, INF = 1e9;
#define int long long
int n, m, q;
int d[N][N];
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]);
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> q;
    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, w;
        cin >> a >> b >> w;
        d[a][b] = min(d[a][b], w);
    }
    floyd();
    while (q--)
    {
        int a, b;
        cin >> a >> b;
        if (d[a][b] > INF / 2)
            cout<<"impossible"<<endl;
        else
            cout << d[a][b] << endl;
    }
}

三重循环