最短路径 - 编程笔记

3.最短路径

单源最短路
多源汇最短路在最短路问题中，源点也就是起点，汇点也就是终点

单源最短路

单源最短路，指的是求一个点，到其他所有点的最短距离。（起点是固定的，单一的）

所有边权都是正数

朴素Dijkstra O(n^2)，基于贪心
堆优化Dijkstra O(mlogn)两者孰优孰劣，取决于图的疏密程度（取决于点数n，与边数m的大小关系）。当是稀疏图（n和m是同一级别）时，可能堆优化版的Dijkstra会好一些。当是稠密图时（m和n^2是同一级别），使用朴素Dijkstra会好一些。

存在负权边

Bellman-Ford O(mn)，基于离散数学，若有负权回路，可能会出现负无穷，即最短路不一定存在
SPFA 一般：O(m)，最坏：O(mn)，比Bellman-Ford用得更多，要求图中不含负环，同时也可以求解正权边的最短路，一些情况下可以代替Dijkstra算法

多源汇最短路

Floyd O(n^3)，基于动态规划

最短路问题的核心在于，把问题抽象成一个最短路问题，并建图。图论相关的问题，不侧重于算法原理，而侧重于对问题的抽象。

（一）Dijkstra

要求的边的权值为正

朴素Dijkstra

主要思想：用一个集合s来存放最短距离已经确定的点。找到1号点到n号点的最短距离，时间复杂度为O(n^2)

初始化距离数组dist表示1号点到某点的距离,1号点到本身的距离为0：dist[1] = 0, 其他dist[i] = 0x3f3f3f3f无穷大
循环n次：每次从距离已知的点中，选取一个不在s集合中，且距离起点最短的点t（这一步后续可以用小根堆来优化），把t加入到集合s中。
然后遍历一下所有边，看加入点t后，t的出边中，是否可以通过以t为中间点缩小与起点的距离，即dist[j]>dist[t]+g[t][j]
当所有点都被遍历完后，判断dist[n]是否还为无穷大，若是则意味着1和n不连通，否则返回dist[n]即为1号点到n号点的最短路距离

朴素Dijkstra对应稠密图，因此用邻接矩阵来存储

AcWing 849. Dijkstra求最短路 I

稠密图（m和n^2是同一级别），用朴素dijkstra

#include <iostream>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
const int N=510;
int g[N][N],dist[N];//dist为到起点的距离
bool s[N];//表示当前点还有加入最短距离集合中
int n,m;

//返回最短距离
int dijkstra(){
    memset(dist,0x3f,sizeof dist);//初始化距离数组
    dist[1]=0;//到本身的距离为0
    for(int i=1;i<=n;i++){
        int t=-1;
        //找到当前不在最短中且距离起点最近的点
        for(int j=1;j<=n;j++){
            if(!s[j] && (t==-1 || dist[t]>dist[j])){ //t=-1一个点都还没
                t=j;
            }
        }
        
        s[t]=true;//标记为加入最短路
        
        //遍历所有点更新到起点的距离
        for(int i=1;i<=n;i++){
            if(dist[j]>(dist[t]+g[t][j]))
                dist[j]=dist[t]+g[t][j];
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;//不存在1到n的最短路
    else return dist[n];
}


int mian(){
    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);//因为图中含有重边和自环 所以每次输入都更新为更小值
    }
    cout<<dijkstra();
    return 0;
}

堆优化Dijkstra

当图为稀疏图时（点数n和边数m是同一数量级时，如下题），使用堆优化的dijkstra，将时间复杂度由O(n^2)降为O(mlogn)

堆可以自己手写（用数组模拟），也可以使用现成的（C++的STL提供了优先队列priority_queue，即可使用大根堆和根堆，但相比手写堆不提供任意元素修改）

AcWing 850. Dijkstra求最短路 II

实现思路：堆优化，构造小根堆得到当前未加入点中和起点距离最小的点

稀疏图，采用邻接表存储图，但额外添加一个权重数组w[]，代表边a和边b的权值
pair<int,int> PII第一个int表示1号点到该点的距离，第二个int就是该点的编号，利用C++STL优先队列建立小根堆priority_queue<PII,vector<PII>,greater<PII>> heap ，存储当前未加入最短路的点的集合
当堆heap不为空时，取出堆顶元素，即当前未加入中距离起点最近的点，根据该点的出边，更新以该点为中间点后各点与起点的距离是否缩小，若缩小就更新
- 更新距离时，可能对一些距离已知的点进行更新（更新为更小的距离），按理说，应该修改堆中对应节点的距离值，但由于优先队列中的堆不支持直接修改某元素的值，则可以直接插入一个新的节点（此时对于同一个节点，堆中有两份，即冗余存储），但没有关系，在默认情况下，std::pair 的比较首先比较第一个元素，如果第一个元素相等，再比较第二个元素。因此，如果两个 pair 的第一个 int 值相同，将会比较第二个 int 值谁更小，因此更新距离后堆顶依旧是目前未加入点中和起点距离最小的点。

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>//优先队列头文件
using namespace std;
typedef pair<int,int> PII;//第一个int是到起点距离，第二个int是当前点的编号
const int N=1e5+10;
int h[N],e[N],ne[N],w[N],idx;//构造邻接表
int dist[N];//到起点的距离
int n,m;
int s[N];//判断当前点是否已加入最短路中

//在a和b中加入一条边，权值为c  构造邻接表
void add(int a,int b,int c){
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;//存储边的权值
    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.fist;//得到编号和距离
        if(s[ver]) continue;//如果已加入最短路则退出 重新取堆顶元素
        s[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];
                heap.push({dist[j],j});//加入堆
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    else return dist[n];
}

int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);//初始化链表
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    cout<<dijkstra();
    return 0;
}

（二）Bellman-Ford

该算法适用于有负权边的情况，注意：如果有负权环的话，最短路就不一定存在了。时间复杂度O(mn)。该算法可以求出来图中是否存在负权回路，但求解负权回路，通常用SPFA算法，而不用Bellman-Ford算法，因为前者的时间复杂度更低。

Bellman-ford不要求用邻接表或者邻接矩阵存储边，为简化操作，可以定义一个结构体，存储a，b，w。表示存在一条边a点指向b点，权重为w。则遍历所有边时，只要遍历全部的结构体数组即可

主要步骤：

循环n次

循环的次数的含义：假设循环了k次，则表示，从起点，经过不超过k条边，走到某个点的最短距离
每次循环，遍历图中所有的边。对每条边(a, b, w)，（指的是从a点到b点，权重是w的一条边）**更新d[b] = min(d[b], d[a] + w)**。该操作称为松弛操作。

该算法能够保证，在循环n次后，对所有的边(a, b, w)，都满足d[b] <= d[a] + w。这个不等式被称为三角不等式。

AcWing 853. 有边数限制的最短路

实现思路：

利用上述的Bellman-ford算法
依旧定义一个距离数组dist，初始化为正无穷(0x3f3f3f3f)、

注意最后判断到n号结点是否有路径不是直接判断dist[n]==0x3f3f3f3f，因为存在负权边，可能更新的时候会存在dist[n]=0x3f3f3f3f-c，即无穷大加上一个负数，仍为无穷大，但数值还是改变了，所以最后是否有路径的判断改为dist[n]>0x3f3f3f3f/2
本题要求1号到n号点不超过k条边的最短距离，则循环k次来寻找最短路。
每次再遍历m条边，判断加入当前点后，各点到起点的距离是否变小，若变小则更新距离

注意：该距离更新时可能会导致参与的边的数量大于k，因此应在每次遍历前设置一个备份数组backup，记录在k次遍历中，本次遍历的上一次的距离数组状态，在该次遍历中对每条边的距离数组更新时采用备份数组，确保本次更新范围在当前的边数限制内。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=510,M=10010;
int dist[N],backup[N];//距离数组和备份数组
int n,m,k;
//定义一个结构数组存储边 
struct Edge{
    int a,b,w;
}edge[M];

int bellman_ford(){
    memset(dist,0x3f ,sizeof dist);
    dist[1]=0;
    for(int i=0;i<k;i++){//限定了最多k条边
        memcpy(backup,dist,sizeof dist);//先将距离数组做一次备份
        //遍历m条边 跟新距离
        for(int j=0;j<m;j++){
            int a=edge[j].a,b=edge[j].b,w=edge[j].w;
            if(dist[b]>(backup[a]+w))//用备份数组更新
                dist[b]=backup[a]+w;
        }
    }
    if(dist[n]>0x3f3f3f3f/2) return -1;
    else return dist[n];
}

int main(){
    cin>>n>>m>>k;
    for(int i=0;i<m;i++){//下标从0开始
        int a,b,w;
        cin>>a>>b>>w;
        edge[i]={a,b,w};
    }
    int t=bellman_ford();
    if(t==-1) cout>>"impossible";
    else cout>>t;
    return 0;
}

（三）SPFA

若要使用SPFA算法，一定要求图中不能有负权回路。只要图中没有负权回路，都可以用SPFA，即也可以求解正权边的题，这个算法的限制是比较小的。时间复杂度为一般为O(m)，最差为O(mn)，在一些情况下可以代替Dijkstra算法

SPFA其实是对Bellman-Ford的一种优化，相比Bellman-Ford判环的时间复杂度也更低。

它优化的是这一步：d[b] = min(d[b], d[a] + w)

我们观察可以发现，**只有当d[a]变小了，在下一轮循环中以a为起点的点（或者说a的出边）就会更新，即下一轮循环必定更新d[b]**（只有我变小了，我后面的点才会变小）

考虑用一个队列queue，来存放距离变小的节点。（当图中存在负权回路时，队列永远都不会为空，因为总是会存在某个点，在一次松弛操作后，距离变小）（和堆优化Dijkstra很像）

AcWing 851. spfa求最短路

实现思路：相比上题没有k条边的限制，所以使用SPFA算法，时间复杂度更低

稀疏图，使用邻接表存储，类似dijkstra
设置一个队列queue（使用C++STL中提供的队列queue）来存储待更新的点，初始将起点入队，同时设置一个数组s[]作为标记，标记该点在队列中，然后在每次遍历中，弹出队头，同时将该点取消标记，循环判断该点的相连的节点距离是否变小，若变小，则更新距离。同时不在队列中，则入队同时标记为已入队

因为遍历过程中可能遍历到的点已经在队列中，但依旧可以更新距离，所以这里的判断不是同时判断距离变小和是否在队列中，要分开判断

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N=1e5+10;
int e[N],ne[N],w[N,h[N],idx;
int dist[N];
int n,m;
bool s[N];//记录是否在队列中

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

int spfa(){
    memset(dist,0x3f,sizeof dist);
    dist[1]==0;
    queue<int> q;//建立一个队列
    q.push(1);//起点入队
    s[1]=true;//入队标记
    while(q.size()){//队列不为空
        auto t=q.front();//获得队头元素
        q.pop();//队头出队
        s[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(!s[j]){
                    s[j]=true;
                    q.push(j);//入队
                }
            }
        }
    }
    if(dist[n]>0x3f3f3f3f/2) return -1;
    else return dist[n];
}                 
                 
                 
int mian(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--){
        int a,b,w;
        cin>>a>>b>>w;
        add(a,b,w);
    }
    int t=spfa();
    if(t==-1) cout<<"impossible";
    else cout<<t;
    return 0;
}

AcWing 852. spfa判断负环

实现思路：

在以上SPFA的基础上，设置一个**记录边数的数组cnt[]**，即代表起点到当前点经过的边数
在每次更新某点到起点最小距离的同时，将该点的cnt数组值加1，即经过的边数多了一条，当该数组的值大于n，则说明存在负环（n个点若不存在环，最多只有n-1条边）。
注意：由于判断的不是从起点开始存在负环，而是全部图中是否存在负环，因此初始要将所有点都放入队列当中。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N=1e5+10;
int e[N],ne[N],w[N,h[N],idx;
int dist[N],cnt[N];//cnt数组记录起点到当前点的边数
int n,m;
bool s[N];//记录是否在队列中

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

bool spfa(){
    memset(dist,0x3f,sizeof dist);
    dist[1]==0;
    queue<int> q;//建立一个队列
    
    //所有点都要先入队
    for(int i=1;i<=n;i++){
        q.push(i);
    	s[i]=true;
    }
    
    while(q.size()){//队列不为空
        auto t=q.front();//获得队头元素
        q.pop();//队头出队
        s[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];
                cnt[j]++;//边数加1
                if(cnt[j]>=n) return true;//存在环
                if(!s[j]){
                    s[j]=true;
                    q.push(j);//入队
                }
            }
        }
    }
   return false;//不存在环
}                 
                 
                 
int mian(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--){
        int a,b,w;
        cin>>a>>b>>w;
        add(a,b,w);
    }
    if(spfa()) cout<<"Yes";
    else cout<<"No";
    return 0;
}

（四）Floyd

求解多源汇最短路问题(任意两点的最短距离)，也能处理边权为负数的情况，但是无法处理存在负权回路的情况。

使用邻接矩阵来存储图

算法思路：三层循环，第一重循环为k，代表中间结点（顺序不可以改变）；后两层循环为i，j（顺序可调换），然后更新d[i][j]=min(d[i][j],d[i][k]+d[k][j])

AcWing 854. Floyd求最短路

注意：本题可能存在重边，因此在读入时要选取更小的权值的边。初始化时，所有d[i][i]=0，其他为正无穷INF

#include <iostream>
#include <algorithm>
using namespace std;
const int N=210,INF=1e9;
int d[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++)
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}

int mian(){
    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];
    }
    return 0;
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。