最短路算法模板总结

图论当中将图为有向图和无向图，这里只考虑有向图的算法。对于无向图，我们将其看做是一种特殊的有向图，对所有的无向边$u\leftrightarrow v$都看做是$u\to v$和$v\to u$。

约定：$n$表示图中点数，$m$表示图中边数。

稠密图：$m$ 与 $n^2$数量级大致相同

稀疏图：$m$ 和 $n$数量级大致相同

建图

一般常用的建图方式有两种：

1. 邻接矩阵：定义二维数组 $g[N][N]$，$g[i][j]$表示点$i$和$j$之间的边权。
2. 邻接表：数组模拟邻接表，为每个节点开一个单链表，分别存储该点的所有邻接边。

特殊的，对于Bellman_ford算法，我们通常定义结构体数组存储所有边的信息。

最短路算法

最短路算法一般分为两类：

1. 单源最短路，常见的算法有：

   $(1)$Dijkstra：只有所有边的边权为正才可以使用，在稠密图中的算法时间复杂度$为O(n^2)$，在稀疏图中的算法时间复杂度为$O(m\times long(n))$。

   $(2)$Bellman_ford：存在负权边时使用，有边数限制的最短路问题，存在负权回路时的最短路问题，时间复杂度为$O(nm)$。

   $(3)$spfa—队列优化的Bellman_ford算法：时间复杂度为$O(m)$，时间复杂度最坏为$O(nm)$。

2. 多源最短路：

   $(1)$​Floyd：标准弗洛伊德算法，三重循环。循环结束之后 $d[i][j]$存储的就是点 $i$ 到点 $j$ 的最短距离。需要注意循环顺序不能变：第一层枚举中间点，第二层和第三层枚举起点和终点。时间复杂度$O(n^3)$。

Dijkstra算法模板（包括堆优化）

朴素Dijkstra

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int n, m;
int g[N][N];
int dist[N];
bool st[N]; // 确定最短路点的集合

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] && (t == -1 || dist[t] > dist[j]))
                t = j;
        
        // 更新其他点
        for(int j = 1; j <= n; j ++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        
        // 标记已确定最短路的点
        st[t] = true;
    } 
}

int main()
{
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            if(i == j) g[i][j] = 0;
            else g[i][j] = INF;
            
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = min(g[a][b], c);
    }
    
    dijkstra();
    
    if(dist[n] == INF) puts("-1");
    else printf("%d\n", dist[n]);
    
    return 0;
}

堆优化版dijkstra

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 150010, INF = 0x3f3f3f3f;

typedef pair<int, int> PII;

int n, m;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool st[N]; // 被确定最短路的点集合

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

void 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;
        
        if(st[ver]) continue;
        st[ver] = true;
        
        for(int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[ver] + w[i])// 邻接边的距离大于用当前点更新的距离时就替换
            {
                dist[j] = dist[ver] + w[i];// d[ver] 是当前最小点的距离; w[i] 是当前邻接边的权重
                heap.push({dist[j], j});
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    
    memset(h, -1, sizeof h);
    
    while(m --)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    
    dijkstra();
    
    if(dist[n] == INF) puts("-1");
    else printf("%d\n", dist[n]);
    
    return 0;
}

Bellman_Ford算法模板

Bellman_Ford

解决有限制边数的最短路问题必须选择Bellman_Ford

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, M = 10010, INF = 0x3f3f3f3f;

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

int n, m, k;
int dist[N], backup[N];

void Bellman_Ford()
{
    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 = edges[j].a, b = edges[j].b, w = edges[j].w;
            dist[b] = min(dist[b], backup[a] + w);
        }
    }
}

int main()
{
    cin >> n >> m >> k;
    
    for(int i = 0; i < m; i ++)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edges[i] = {a, b, w};
    }
    
    Bellman_Ford();
    
    if(dist[n] > INF / 2) puts("impossible");
    else printf("%d\n", dist[n]);
    
    return 0;
}

spfa（队列优化Bellman_Ford）算法模板

spfa算法求解最短路

spfa算法与堆优化Dijkstra算法类似，在一般情况下spfa巨快

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010, INF = 0x3f3f3f3f;

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

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

void 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])
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    
    memset(h, -1, sizeof h);
    
    while (m -- )
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        add(a, b, w);
    }
    
    spfa();
    
    if(dist[n] > INF / 2) puts("impossible");
    else printf("%d\n", dist[n]);
    
    return 0;
}

Floyd算法模板

Floyd算法模板题

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210, INF = 0x3f3f3f3f;

int g[N][N];
int n, m, Q;

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

int main()
{
    scanf("%d%d%d", &n, &m, &Q);
    
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            if(i == j) g[i][j] = 0;
            else g[i][j] = INF;
            
    while(m --)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = min(g[a][b], c);
    }
    
    floyd();
    
    while(Q --)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        if(g[x][y] > INF / 2) puts("impossible");
        else printf("%d\n", g[x][y]);
    }
    
    return 0;
}