[图论]万字解析图的最短路算法(详细带图解和代码)

图的存储方式

图主要有以下两种表示方法：邻接矩阵和邻接表（注意，本文仅讨论有向图的情况）

领接矩阵

假设我们有以下的图

每个圈表示一个图中节点，圈里面的数字表示此节点编号，每个边都有权重

我们可以用一个二维数组存储这个图：设此二维矩阵的某个点为$g[i][j]$。那么$g[i][j]$的值就表示从$i$到$j$的距离

上图我们就可以存储为以下形式

其中，不通的点我们用INF表示,且$INF=+\infty$
第一行第三列的数据表示：从$1$号点到$3$号点的距离为$4$
以此类推

此方法适合用于存储稠密图（边数多于结点数的情况）

领接表

每个点有很多出边，我们可以定义结点数量个单链表，每一个单链表存储这个结点能到哪些边，且权值是多少

比如上面的图我们可以这样存储

$1$号单链表的含义为：从$1$号点出发，能走到$2$，$3$结点。$2$号链表表示$2$号结点只能走到$3$号结点，$3$号链表表示$3$号结点不通任何路。

那么就很清楚了，我们需要一系列单链表存储图，本文中单链表的定义方式并不是传统的以下形式

struct ListNode
{
	int val;
	ListNode* next;
};

为了提高内存命中率和运算效率，我们在这里利用数组来模拟单链表

const int N;//表示最大结点数
int e[N];//存储每个结点给元素
int ne[N];//利用数组下标表示当前结点的下个结点的小标
int h[N];//初始全为-1，-1表示空结点
int idx;//遍历结点的指针

这种形式的单链表，如果我们需要在里面头插一条边，可以这么实现

//插入a->b，其权值为c
void add(int a,int b,int c)
{
	e[idx]=b;//在数组下标idx中插入结点信息b
	ne[idx]=h[a];//idx位置的元素（b）的后一个结点的下标位置是h[a](a的头结点)
	h[a]=idx;//a号链表头结点设置为b
	w[idx]=c;//设置权值为c
	idx++;//指针+1
}

图解（以插入$1$，$2$，$2$为例）

此方法适合用于存储稠密图（边数少于结点数的情况）

上述内容只是下面内容的铺垫，让我们正式进入今天的重头戏：最短路算法！

最短路算法

知识框架

本文将介绍以下算法

这里总结一下新概念

• 单源最短路径：求出固定一个点到任意一个点经过的最短路径
• 多源最短路径：能求出任意两个点的最短路径

单源最短路径

路径权值全为正数

dijkstra算法（版本1）

这是这个算法的最直接的实现版本，适合用于稠密图

本人文笔有限，不能直接直接用文字说明算法，让我们边画图边用文字说明吧~

假设我们有以下图

此图的领接矩阵可表示为

这个算法的核心思想是：开辟一个距离数组$d[N]$。它用于保存当前从起点到这个点的最短距离，初始此数组全部设为INF，表示从起点到终点没有路径

注意：本文默认起点为编号1的点

另外开辟一个布尔数组，标记当前这个点是否已经找到了最短路径

int d[N];//默认全为INF,表示从起点没有路径经过
bool st[N];//默认全是false，表示当前这个点没有找到最短路径

刚开始的状态如下图

算法开始执行时，我们要先处理起点的信息，起点到自己的距离肯定是0，并且起点到起点一定是最短的路径

然后，我们遍历当前最短路径点所有的边，看看从这个点延伸出去的路径情况

$1$能到达点$2$，$3$。更新d数组

更新的同时，记录当前的最短路径到达的点是哪个，并记录
例如当前的最短距离是2这个结点
我们就认为，已经找到了从1为起点，终点为2的最短路径，距离是2（这里本文不作证明）
将2结点的状态记录为true表示已经找到了最短路径

然后。从上一步找到的当前最好结点，也就是2结点出发，遍历它的所有边
只有$2\to 3$这一个边，而$1\to 2,2\to 3$这个路径比$1\to 3$这个路径好，我们进行更新

最后遍历，发现当前只有3这个点为false了，最后把它设置为true，至此，全部执行完毕

本文的算法伪代码如下：

for(int i=1;i<=n;i++)//遍历所有点
{
	int t=-1;//记录当前找到的最短结点
	for(int j=1;j<=n;j++)
	{
		if(!st[j]&&(t==-1||d[j]<d[t]))t=j;//如果当前点没有找到最短路径，并且它比目前记录的最小路径还要小，将其更新为最短路径
	}
	st[t]=true;//当前点找到了最短路径
	//下面利用最短路径点更新每个点的最短路径
	for(int j=1;j<=n;j++)
	{
		d[j]=min(d[j],d[t]+g[t][j]);//看经过当前最短路径点的路径是否比已经记录的路径还要小，如果是，则更新
	}
}

我们通过一个例题，来实现本小节的算法

题目来源：acwing849

本题纯裸题，就是对我们上文的算法进行代码实现
不过有几个细节需要注意：

• 处理重边：我们只需要在输入中，记录最小的边即可，因为重边中如果有较大的边，一定不会采用
• 处理自环：判断即可，如果输入是一个自环，跳过记录即可

代码实现如下，具体细节请查看注释

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

using namespace std;

const int N = 510;

const int INF=0x3f3f3f3f;//此常数表示无穷大

int g[N][N],d[N],n,m;//d存储从1到i的最短路径
bool st[N];//存储哪些点已经有了最短路径

int dij()
{
    d[1]=0;
    for(int i=1;i<=n;i++)
    {
        int t=-1;//记录从i出发，哪个点最短
        for(int j=1;j<=n;j++)
        {
            if(!st[j]&&(t==-1||d[t]>d[j])) t=j;//如果j不是最短路并且j比t的路径还短，更新最短路径点为j
        }

        //更新从t出发的路径情况
        for(int j=1;j<=n;j++)
        {
            d[j]=min(d[j],d[t]+g[t][j]);
        }

        st[t]=true;//找到最短路径了，设置为true
    }

    if(d[n]==INF) return -1;
    return d[n];
}


int main()
{
    cin>>n>>m;
    memset(g,INF,sizeof g);
    memset(d,INF,sizeof d);
    for(int i=0;i<m;i++)
    {
        int a,b,s;
        scanf("%d%d%d",&a,&b,&s);
        if(a==b) continue;//处理自环
        else g[a][b]=min(g[a][b],s);//处理自环
    }

    cout<<dij()<<endl;
    return 0;
}

算法文字描述
遍历$n$个点
判断当前哪个路径最短，更新并记录最短路径和最短路径点
利用当前最短路径点更新其它点的路径信息（要经过当前路径点的）

时间复杂度
遍历$n$个点的同时，每次要遍历n个路径点，以找到最短路径点

所以时间复杂度为$O(n^2)$

dijkstra(堆优化版本)

我们发现，上面的算法中，每次在找当前最短路径点时，都是从$1$到$n$暴力的去找

有没有一种方式，能够更快的找到当前的最短路径点呢？

它就是优先级队列！(不懂优先级队列的可以自己去查，本文不作介绍，默认读者都会使用)

我们可以每次把当前最短路径设置到队头位置，这样就能以$logn$级别的时间复杂度找到当前最短路径点，而不用一个点一个点的遍历来寻找最短路径点

同样用一个例题来实现一下

原题链接.acwing850

本题的图是稀疏图，所以使用邻接表的方式存储数据

除了寻找最短路径点的方式，其它的思想基本一样，具体细节请参见代码注释

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


using namespace std;
typedef pair<int, int> PII;//使用{路径，当前点的方式}表示一个点的信息
//路径在前的原因：优先级队列优先以pair的第一个元素进行比较

const int N = 1e6+10;
const int INF=0x3f3f3f3f;
int e[N],ne[N],h[N],idx,n,m,w[N];
int d[N];
bool st[N];

//往图中添加a->b，路径权值为c的点
void add(int a,int b,int c)
{
    e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}

int dij()
{
    d[1]=0;
    priority_queue<PII,vector<PII>,greater<PII>>pq;
    pq.push({0,1});
    
    while(!pq.empty())
    {
        auto t=pq.top();
        pq.pop();
        //直接从队头取到当前的最短路径点
        int dist=t.first;
        int var=t.second;
        
        if(st[var]) continue;//如果当前点已经被找到了，不执行更新
        st[var]=true;
        
        //利用最短点更新路径信息
        for(int i=h[var];i!=-1;i=ne[i])
        {
            int j=e[i];
            
            if(d[j]>d[var]+w[i])
            {
                d[j]=d[var]+w[i];
                pq.push({d[j],j});
            }
        }
        

    }
    
    if(d[n]==INF) return -1;
    return d[n];
}


int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    memset(d,INF,sizeof d);
    
    for(int i=0;i<m;i++)
    {
        int a,b,s;
        scanf("%d%d%d",&a,&b,&s);
        add(a, b, s);
    }
    
    cout<<dij()<<endl;
    return 0;
}

时间复杂度

更新$m$个点的信息($m$表示边数),每次更新需要消耗$logn$的时间（堆更新的时间复杂度）

总时间复杂度为$O(mlogn)$

上面的算法只适用于边权全为正数的情况，如果边权为负数，上面的算法将失效（本文不作证明）

所以必须要介绍能求出存在负权值的图的最短路径的算法

路径权值存在负数

bellmanFord算法

此算法比较朴素，核心思想是存储每一条边的信息，遍历每个点的同时遍历每个边来更新路径信息

本算法需要遍历每一条边，所以我们怎么方便存储边信息怎么来，甚至可以用一个结构体存储

//表示a->b，权值为c的边（c可能为负数）
struct edge
{
	int a;
	int b;
	int c;
};

同样边上图边分析,设我们有以下图,与迪杰斯特拉算法类似，需要用数组存储每个点到起点的最短路径
设要求从1到4的最短路径(大家可以心算一下，最短路径应该是$1\to 2\to 3\to 4$，距离为1)

距离数组仍然初始全部设为$+\infty$，起点设置为$0$

当前遍历到点$1$，更新所有边的信息
更新边信息的方式：利用松弛操作

具体的说，如果表格中记录的当前最短路径比起点$\to$当前边起点$\to$当前边终点这条路径要长，就把最短路径信息更新为后者

比如当前图，我们遍历4条边:$1\to 2,2\to 4,2\to 3,3\to 4$
$1\to 2$这条边比$INF$小，更新距离为$1$

以此类推，更新所有信息
注意，我们这里应该拿更新前的数组作为依据来更新距离（起点$\to$当前边起点$\to$当前边终点这条距离中，起点距离应该设为此轮更新前），具体原因后面说

此轮未更新，进入下一轮，每一轮都需要遍历所有边

$2$为起点，可以更新$3$和$4$点的信息

下一轮，只有$3\to 4$需要更新

此算法的伪代码如下

for(点数次循环)
{
	for(遍历所有边)
	{
		if(某一点从起点到终点的距离比起点->当前遍历到的边起点->当前遍历到的边终点（某一点）要长)
        {
            将距离更新为后者
        }
	}
}

接下来解答几个疑问

1 为啥要准备两个数组，为啥更新要以这一轮更新前的数组为依据？
答：为了防止串联

以下面这个图举例

假如我们要更新从1分别到2，3的最短距离。正确结果应该是1和3才对

如果我们用当前数组更新结果，$1\to 2$结果是1，数组2的位置是1.

此时我们如果更新3的信息，实际会利用$2\to 3$这条边来更新，结果为$1+1=2$

但实际情况应该是$1\to 3$，距离为3

这就导致了错误，如果我们用更新前的结果(2为$+\infty$)就不会导致这个问题

2 如何判断存在负权回路？

负权回路，形如下面的图。$1\to 2\to 3$是一个环路，从环路中每走一圈，其总距离就会减小

判断父权回路利用了抽屉原理(本文不作介绍)，具体来说

设$1$到$n$可到达，那么通过$n-1$次操作，一定能找到最短距离，如果超过了这个次数，数组还能继续更新，则说明存在了负权回路

所以，只需要记录操作次数就行了
另外，如果存在负权回路，那么从1到n的路径肯定是$-\infty$

3 如果$1\to n$不存在路径，还能用$+\infty$进行比较吗？

不能了，因为无穷大也可能被操作

形如下面的情况，设终点为n，并且n-1一定不可到达

在更新时，因为INF-1比INF小，所以n的距离会被更新为INF-1
虽然它在形式上仍为不可到达的无穷大，但它确实已经不等于INF了

可以利用以下的判断形式

$$d>\frac{+\infty }{2}$$

具体题目实现

题目来源acwing853

很朴素的裸题，没啥注意的，直接看代码就行了

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

using namespace std;

const int N = 510;
const int M=10010;
const int INF=0x3f3f3f3f;
int n,m,k,d[N],backup[N];

struct edge
{
    int a;
    int b;
    int c;
}ee[M];//利用结构体存储边的信息

void bellman()
{
    d[1]=0;
    
    for(int i=0;i<k;i++)//求k条边就遍历k次
    {
        memcpy(backup,d,sizeof d);//备份上一次的状态
        for(int j=0;j<m;j++)//遍历每一条边
        {
            int a=ee[j].a,b=ee[j].b,c=ee[j].c;
            d[b]=min(d[b],backup[a]+c);//利用上一次的状态更新距离信息
        }
    }
}

int main()
{
    cin>>n>>m>>k;
    
    memset(d,INF,sizeof d);
    for(int i=0;i<m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        ee[i]={x,y,z};
    }
    
    bellman();
    
    if(d[n]>INF/2) cout<<"impossible"<<endl;
    else cout<<d[n]<<endl;
    return 0;
}

时间复杂度

$$O(nm)$$其中n为点数m为边数

spfa算法（基于bellmanFord的优化）

我们注意到上面的算法，每次都要遍历所有的边，感觉太笨了
尤其是解答疑问环节的第三种情况，明明不可到达了，却还在更新

能不能优化寻找边的方法，让它可以不用每次傻乎乎的遍历所有的边，又能得到正确的信息呢？

spfa算法就是基于寻找边方法的优化，具体来说，它利用了BFS（宽度优先搜索）的思想(本文不介绍BFS，不懂的自己去搜)

具体来说，只有当前点得到更新的情况下，利用BFS找到它的所有边，并进行更新

如果当前点不可到达或没有更新，说明它对最终答案没有贡献，此轮就暂时不会用它的边来更新其它点的距离信息

BFS利用队列存储需要处理的点的信息即可

解答一些疑问

1 看你的代码，好像这个跟迪杰斯特拉算法很像啊？

其实是有差别的，具体就在 st[N] 这个数组上

回忆一下，迪杰斯特拉算法中的这个数组是用来判断当前点是否已经找到了最短路径，是不可逆的

而这个算法中的这个数组只是判断一下当前信息是否入队，如果入队就不用反复入队了，但未来还可能用到这个结点，是可逆的

2 判断不可到达的方式

这里还是使用$d=+\infty$,因为不可到达的点在此算法中得不到更新

3 有负权回路怎么办？

此代码没有添加判断负权回路的方法，会死循环，如果需要，开辟一个计数数组即可，利用上一小节提到的方法判断即可

题目来源acwing851

代码实现，细节请参见注释

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


using namespace std;

const int N = 100010;
const int INF=0x3f3f3f3f;

//使用邻接表存储图
int e[N],ne[N],h[N],w[N],idx,n,m,d[N];
bool st[N];
queue<int>q;

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

void spfa()
{
    d[1]=0;
    q.push(1);
    st[1]=true;
    //处理起点
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        
        st[t]=false;//当前点出队了
        //bfs思想，遍历当前点的所有出边
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(d[j]>d[t]+w[i])//更新距离点的条件
            {
                d[j]=d[t]+w[i];
                if(!st[j])//如果当前点不在队列中就更新
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    
    
}



int main()
{
    memset(h,-1,sizeof h);
    memset(d,INF,sizeof d);
    
    cin>>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(d[n]==INF)cout<<"impossible"<<endl;
    else cout<<d[n]<<endl;
    return 0;
}

本算法对适合用迪杰斯特拉算法的题目也同样使用

多源最短路径(Floyd算法)

此算法很简单暴力，设我们要求$i\to j$的最短路径

我们遍历每一个点，设当前点为$k$

判断从$i\to j$的当前距离是否比经过$k$点的距离要大，如果大，则认为如果要从i到j，经过k这个点比原来的情况更好，利用k更新路径信息

本题思想很简单，所以不需要进行额外说明，直接上代码吧,实现细节可以参见注释

acwing854题

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

using namespace std;

const int N = 210;
const int INF=0x3f3f3f3f;
int n,m,k;
int d[N][N];//d[i][j]表示从i到j的最短距离

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()
{
    cin>>n>>m>>k;
    
    memset(d,INF,sizeof d);
    
    for(int i=1;i<=n;i++) d[i][i]=0;
    
    for(int i=0;i<m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        d[x][y]=min(d[x][y],z);
        
    }
    floyd();
    
    while(k--)
    {
        int x,y;
        scanf("%d%d", &x, &y);
        
        if(d[x][y]>INF/2) printf("impossible\n");
        else printf("%d\n",d[x][y]);
    }
    
    return 0;
}

参考文章

Dijkstra求最短路 I：图解 详细代码（图解）
AcWing 853. 有边数限制的最短路
AcWing 853. 有边数限制的最短路-2
AcWing 851. SPFA算法
非常感谢！