最短路算法模板（Dijkstra、Bellman_ford、spfa、Floyd）

最短路算法模板总结

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

    u
   
   
    ↔
   
   
    v
   
  
  
   u \leftrightarrow v
  
 
u↔v都看做是

 
  
   
    u
   
   
    →
   
   
    v
   
  
  
   u\to v
  
 
u→v和

 
  
   
    v
   
   
    →
   
   
    u
   
  
  
   v \to u
  
 
v→u。

约定：

    n
   
  
  
   n
  
 
n表示图中点数，

 
  
   
    m
   
  
  
   m
  
 
m表示图中边数。

稠密图：

    m
   
  
  
   m
  
 
m 与 

 
  
   
    
     n
    
    
     2
    
   
  
  
   n^2
  
 
n2数量级大致相同

稀疏图：

    m
   
  
  
   m
  
 
m 和 

 
  
   
    n
   
  
  
   n
  
 
n数量级大致相同

建图

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

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

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

最短路算法

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

1. 单源最短路，常见的算法有： ( 1 ) (1) (1)Dijkstra：只有所有边的边权为正才可以使用，在稠密图中的算法时间复杂度 为 O ( n 2 ) 为O(n^2) 为O(n2)，在稀疏图中的算法时间复杂度为 m l o n g ( n ) mlong(n) mlong(n)。 ( 2 ) (2) (2)Bellman_ford：存在负权边时使用，有边数限制的最短路问题，存在负权回路时的最短路问题，时间复杂度为 O ( n m ) O(nm) O(nm)。 ( 3 ) (3) (3)spfa—队列优化的Bellman_ford算法：时间复杂度为 O ( m ) O(m) O(m)，时间复杂度最坏为 O ( n m ) O(nm) O(nm)。
2. 多源最短路： ( 1 ) (1) (1)​Floyd：标准弗洛伊德算法，三重循环。循环结束之后 d [ i ] [ j ] d[i][j] d[i][j]存储的就是点 i i i 到点 j j j 的最短距离。需要注意循环顺序不能变：第一层枚举中间点，第二层和第三层枚举起点和终点。时间复杂度 O ( n 3 ) O(n^3) O(n3)。

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

朴素Dijkstra

#include<iostream>#include<cstring>#include<algorithm>usingnamespace std;constint N =510, INF =0x3f3f3f3f;int n, m;int g[N][N];int dist[N];bool st[N];// 确定最短路点的集合voiddijkstra(){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;}}intmain(){
    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");elseprintf("%d\n", dist[n]);return0;}

堆优化版dijkstra

#include<iostream>#include<cstring>#include<algorithm>#include<queue>usingnamespace std;constint 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];// 被确定最短路的点集合voidadd(int a,int b,int c){ 
    e[idx]= b, ne[idx]= h[a], w[idx]= c, h[a]= idx ++;}voiddijkstra(){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});}}}}intmain(){
    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");elseprintf("%d\n", dist[n]);return0;}

Bellman_Ford算法模板

Bellman_Ford

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

#include<iostream>#include<cstring>#include<algorithm>usingnamespace std;constint N =510, M =10010, INF =0x3f3f3f3f;structEdge{int a, b, w;}edges[M];int n, m, k;int dist[N], backup[N];voidBellman_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);}}}intmain(){
    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");elseprintf("%d\n", dist[n]);return0;}

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

spfa算法求解最短路

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

#include<iostream>#include<cstring>#include<algorithm>#include<queue>usingnamespace std;constint N =100010, INF =0x3f3f3f3f;int n, m;int h[N], e[N], ne[N], w[N], idx;int dist[N];bool st[N];voidadd(int a,int b,int c){
    e[idx]= b, ne[idx]= h[a], w[idx]= c, h[a]= idx ++;}voidspfa(){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);}}}}}intmain(){
    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");elseprintf("%d\n", dist[n]);return0;}

Floyd算法模板

Floyd算法模板题

#include<iostream>#include<cstring>#include<algorithm>usingnamespace std;constint N =210, INF =0x3f3f3f3f;int g[N][N];int n, m, Q;voidfloyd(){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]);}intmain(){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");elseprintf("%d\n", g[x][y]);}return0;}