图论中的最短路问题

JoshWindsor · 发表于 2022-1-10 12:38

常见的有向图最短路问题可以分为两大类：

单源最短路：求一个点到其他所有点的最短距离，它又可以分为如下的几种情况
多源汇最短路：任选图中两个点作为起点和终点，求从起点到终点的最短距离

（无向图是特殊的有向图，因此接下来介绍的算法同样适用）
这两大类又可以根据下图所示的情况分为一些小类

假定n是图中的点数，m是图中的边数，朴素Dijkstra算法的时间复杂度是O(n^2)，和边数无关，堆优化版的Dijkstra算法的时间复杂度是O(mlog(n))，对于稠密图，其边数m和n^2一个级别，因此更适合使用朴素Dijkstra(可以将m=n^2代入这两个时间复杂度公式进行比较)，对于稀疏图来说，其边数和n一个级别，更适合堆优化版Dijkstra(假定m和n都是10^5，代入两个时间复杂度公式进行计算，可以看到堆优化版的时间复杂度明显更低)
SPFA可以看作对Bellman-Ford的优化，但并不是所有情况下都可以使用SPFA解决，e.g. 如果我们对经过的边数做限制，令其不多于k，就只能用Bellman-Ford来解决
接下来逐一介绍上述的算法
朴素Dijkstra

朴素Dijkstra的第一步是要初始化出发点到各个点的距离，dist[1]=0，其余的dist=+∞
之后是一个循环，伪代码如下（其中集合S代表所有当前已经确定最短距离的点）
for i:1~n
  t<-不在S中的距离最近的点
  S<-t
  用t更新其他点的距离(对于所有和t的出边相连的点x，t到x的边的权重是w，判断是否有dist[x]>dist[t]+w，如果是这样则更新dist[x])当循环结束时就可以确定出每个点到起点的最短距离，外层循环的时间复杂度是O(n)，内层循环(找到不在S中的距离最近的点之后再更新所有从这个点可以走到的点的当前最短距离)的时间复杂度也是O(n)，因此总的时间复杂度是O(n^2)
朴素Dijkstra算法适用于稠密图，稠密图使用邻接矩阵来存储，接下来结合如下的问题介绍具体的代码实现和模板

代码实现如下
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 510;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int 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;
      }
      st[t] = true;
      for(int j=1; j<=n; j++)
         dist[j] = min(dist[j], dist[t]+g[t][j]);
}
if(dist[n]==0x3f3f3f3f) return -1;
return dist[n];
}

int main()
{
scanf(&#34;%d%d&#34;, &n, &m);
memset(g, 0x3f, sizeof g);
while(m--)
{
      int a, b, c;
      scanf(&#34;%d%d%d&#34;, &a, &b, &c);
      g[a] = min(g[a], c); //这么做是因为图中有可能存在重边
}
int t = dijkstra();
printf(&#34;%d\n&#34;, t);
return 0;
}
堆优化版Dijkstra

对于稀疏图，适合使用堆优化版Dijkstra算法，该算法本质上是对朴素Dijkstra的优化，我们首先来分析一下朴素Dijkstra的性能瓶颈，如下图所示

可以看到，朴素Dijkstra的性能瓶颈主要在于每次循环时从S集合中找出距离最近的点的方法，朴素方法里采取了时间复杂度是O(n)的枚举比较，而实际上，采用堆这样的数据结构，从一个集合中拿出值最小的元素，时间复杂度可以减小到O(1)
由于每次修改堆中的数据的时间复杂度是O(log(n))，因此上图中每次循环的最后一步加起来总共的时间复杂度就会从O(m)变成O(m * log(n))
因此，如果我们采用堆来存储图中所有点到起点的最短距离，时间复杂度就是O(m * log(n))
对于此处的堆的实现方式，我们可以手写堆，好处是时刻可以保证堆里只有n个数，笔者在下面这篇Blog中实现过
https://zhuanlan.zhihu.com/p/422197633
但代码实现比较复杂，
我们也可以使用STL中的优先队列，和堆类似，但优先队列不支持修改任意一个元素这样的操作，我们只能在每次修改后向优先队列里插入一个新的数，采用这样一个冗余的实现方式，坏处就是这个优先队列中的元素个数最多有m个（可以在后面的代码中看到，这个优先队列是动态维护的），并且我们在每次从优先队列中取出元素时都要检查取出的元素是不是冗余备份（e.g. x号点的距离被存入了堆中两次，分别是更新前和更新后的距离，第二次取出x号点的距离时，我们应该ignore这个无效数据），在后面的代码实现中可以看到
因为优先队列最多有m个元素，所以时间复杂度会变成O(m * log(m))，但由于边数m一般小于n^2，因此log(m)<=log(n^2)=2*log(n)，时间复杂度和手写堆还是一个级别的
因此我们只需使用STL中的优先队列就好了，接下来结合代码分析，由于是稀疏图，所以存储方式改成邻接表，代码如下
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

typedef pair<int, int> PII; //用于存储<节点距离，节点编号>

const int N = 1000010;

int n, m, idx;
int h[N], e[N], ne[N];
int w[N]; //w数组表示边的权重
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)
      {
         int j=e;
         if(dist[j] > distance+w)
         {
            dist[j] = distance + w;
            heap.push({dist[j], j});
         }
      }
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}

int main()
{
scanf(&#34;%d%d&#34;, &n, &m);
memset(h, -1, sizeof h);
while(m--)
{
      int a, b, c;
      scanf(&#34;%d%d%d&#34;, &a, &b, &c);
      add(a, b, c);
}
int t = dijkstra();
printf(&#34;%d\n&#34;, t);
return 0;
}Bellman-Ford算法

Bellman-Ford算法的伪代码如下
for n次
for 所有边(a, b, w) //三元组的含义是(起点，终点，边权)
      dist = min(dist, (dist[a]+w))注意，在Bellman-Ford算法中，可以不使用邻接表这种传统的方式表示图中的边，可使用简单的结构体数组表示，如下所示
struct{
int a, b, w //起点，终点，边权
}edge[M]
如果有负权回路，那么最短路不一定存在，如下图所示

从2号点到3号点到4号点的这三条边构成的这个回路是负权回路，总的权值是-1，如果绕这个回路走很多圈的话，走过的总路径长度可以是负数乃至负无穷
外层循环迭代k次得到的dist数组是有一定的意义的，代表着从起点出发，经过不超过k条边，到各个点的最短距离
如果外层循环的第n次迭代中还有点的最短距离被更新，根据上面的理论，可以得知，从起点到该点的最短距离，经过了n条边，即经过了n+1个点，但图中只有n个点，那么路径中一定存在负环，因此Bellman-Ford算法可以用来找图中的负环，但对于找负环来说，一般使用SPFA算法，在后面会介绍
Bellman-Ford算法的时间复杂度是O(n*m)，即外层循环数 * 内层循环数，下面结合算法题目介绍其具体实现

并且由于这个问题对经过的边数有限制，所以只能用Bellman-Ford，而不能用SPFA
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 510, M = 10010;

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

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

int bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

for(int i=0; i<k; i++)
{
      memcpy(backup, dist, sizeof dist); //备份dist数组
      for(int j=0; j<m; j++)
      {
         int a = edges[j].a;
         int b = edges[j].b;
         int w = edges[j].w;
         dist = min(dist, backup[a]+w);
      }
}
if(dist[n]>0x3f3f3f3f/2) return -1; //因为图中存在负权边，所以更新dist数组时有可能让+∞加上一个负值
return dist[n];
}

int main()
{
scanf(&#34;%d%d%d&#34;, &n, &m, &k);

for(int i=0; i<m; i++)
{
      int a, b, w;
      scanf(&#34;%d%d%d&#34;, &a, &b, &w);
      edges = {a, b, w};
}
int t = bellman_ford();

if(t==-1) puts(&#34;impossible&#34;);
else printf(&#34;%d\n&#34;, t);

return 0;
}
注意，在实际的代码实现中，每次外层循环迭代的一开始，都要备份dist数组，否则在这次的外层的内部枚举所有边时发生串联，如下图的红色字所示

因此我们在代码中使用backup数组作为dist的备份，存储外层循环上一次迭代得到的结果，这样就可以避免串联
SPFA算法

只要图中没有负环，不对经过的边数做限制，就可以使用SPFA算法
SPFA本质上是对Bellman-Ford算法的优化，Bellman-Ford中每次迭代中要遍历所有边来更新dist数组，但实际上在每次迭代中并不是dist数组的所有元素都会被更新，我们分析一下完成dist数组元素更新的代码

可以看出，在当前的迭代中，dist被更新的前提是在上一次迭代里dist[a]被更新了，只有点a本身被更新了，它后继的点b才有可能被更新
因此SPFA基于宽度优先搜索进行优化，每次迭代借助一个队列来完成，队列中存储距离被更新了的点，伪代码如下
queue <- 1号点(起点)
while(queue不空)
{
t <- q.front
q.pop();

更新t的所有出边，
若成功更新则把该出边通向的点加入队列，
加入之前还要判断一下队列中是否已经有这个点，以免重新加入
}接下来结合具体问题介绍其代码实现

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

using namespace std;

typedef pair<int, int> PII;

const int N = 1000010;

int n, m, idx;
int h[N], e[N], ne[N];
int w[N];
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)
      {
         int j =e;
         if(dist[j]>dist[t]+w)
         {
            dist[j] = dist[t]+w;
            if(!st[j])
            {
                  q.push(j);
                  st[j] = true;
            }
         }
      }
}
return dist[n];
}

int main()
{
scanf(&#34;%d%d&#34;, &n, &m);
memset(h, -1, sizeof h);
while(m--)
{
      int a, b, c;
      scanf(&#34;%d%d%d&#34;, &a, &b, &c);
      add(a, b, c);
}
int t = spfa();

if(t==0x3f3f3f3f) puts(&#34;impossible&#34;);
else printf(&#34;%d\n&#34;, t);
return 0;
}
前面说过，SPFA算法也可以用于判断图中是否存在负环，接下来结合下面这个问题来介绍具体的实现

我们为了判断是否存在负环，需要维护两个数组，一个是前面一直使用的用于记录当前最短距离的dist数组，此外还需要维护一个cnt数组，cnt[x]记录从起点到x号点经的边数，我们在每次更新dist数组时也同时更新cnt数组，代码如下
dist[x] = dist[t] + w;
cnt[x] = cnt[t] + 1;
如果经过某一次更新，发现cnt[x]>=n，那么根据前面Bellman-Ford中有关负环的结论（实际上也就是抽屉原理，经过了n个边那就经过了n+1个点，而图中一共就n个点，那么一定经过了某个点两次从而得到了最短路径），图中必定存在负环
因此代码如下
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 2010, M = 10010;

int n, m;
int h[N], w[M], e[M], ne[M], idx;
int dist[N], cnt[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 ++ ;
}

bool spfa()
{
queue<int> q;

for (int i = 1; i <= n; i ++ )
{
      st = true;
      q.push(i);
}

while (q.size())
{
      int t = q.front();
      q.pop();

      st[t] = false;

      for (int i = h[t]; i != -1; i = ne)
      {
         int j = e;
         if (dist[j] > dist[t] + w)
         {
            dist[j] = dist[t] + w;
            cnt[j] = cnt[t] + 1;

            if (cnt[j] >= n) return true;
            if (!st[j])
            {
                  q.push(j);
                  st[j] = true;
            }
         }
      }
}

return false;
}

int main()
{
scanf(&#34;%d%d&#34;, &n, &m);

memset(h, -1, sizeof h);

while (m -- )
{
      int a, b, c;
      scanf(&#34;%d%d%d&#34;, &a, &b, &c);
      add(a, b, c);
}

if (spfa()) puts(&#34;Yes&#34;);
else puts(&#34;No&#34;);

return 0;
}
有几点要注意，dist数组我们可以不初始化，因为我们的目的不是求出最短距离而是判断有无负环，同时，由于是判断图中的负环，而不是将1号点作为起点出发经过的路径上的负环，因此我们一开始要将图中所有点放入队列
Floyd算法

Floyd算法用来解决多源汇最短路问题，使用邻接矩阵存储图，我们这里假设使用二维数组d，d[j]的值是从i号点到j号点的距离，Floyd算法的模板如下
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
         d[j]=min(d[j],d[k]+d[k][j]);
显而易见，时间复杂度是O(n^3)，这三层循环结束之后，d数组的d[j]存储的就是图中从i号点到j号点的最短路的长度，而且这三层循环里，一定要先循环k，i和j的顺序可以随意颠倒
还要注意，Floyd不可以处理有负权回路的图
最后结合具体问题实现这个算法

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

using namespace std;

const int N = 210, INF = 1e9;

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[j] = min(d[j], d[k] + d[k][j]);
}

int main()
{
scanf(&#34;%d%d%d&#34;, &n, &m, &Q);

for (int i = 1; i <= n; i ++ )
      for (int j = 1; j <= n; j ++ )
         if (i == j) d[j] = 0; //应对自环
         else d[j] = INF;

while (m -- )
{
      int a, b, c;
      scanf(&#34;%d%d%d&#34;, &a, &b, &c);
      d[a] = min(d[a], c); //应对重边
}

floyd();

while (Q -- )
{
      int a, b;
      scanf(&#34;%d%d&#34;, &a, &b);

      int t = d[a];
      if (t > INF / 2) puts(&#34;impossible&#34;);
      else printf(&#34;%d\n&#34;, t);
}

return 0;
}
Reference:
http://www.acwing.com

		自动登录	找回密码
密码			立即注册

图论中的最短路问题

本帖子中包含更多资源