本文总结算法中涉及图的最短路径可能用到的算法,主要分为两大类,一类是单源最短路径,即计算一个给定的顶点到其他顶点的最短路径,一类是多源最短路径,即计算顶点两两之间的最短路径。

单源最短路径:

  • Dijkstra 算法
  • Bellman-Ford 算法
  • SPFA 算法

多源最短路径:

  • Floyd 算法
  • Johnson 全源最短路径算法

Dijkstra 算法

Dijkstra 算法用来计算边权均非负的单源最短路径算法。

流程

算法输入图、起点

将顶点分成两个集合:已确定最短路长度的点集(记为 $S$ 集合)的和未确定最短路长度的点集(记为 $T$ 集合)。一开始所有的点都属于 $T$ 集合。

初始化 $dis(s) = 0$,其他点到源点的距离均为 $\infty$。

然后重复这些操作:

  1. 从 $T$ 集合中,选取当前最短路长度最小的点,移到 $S$ 集合中。
  2. 对那些刚刚被加入 $S$ 集合的结点的所有出边执行松弛操作。

直到 $T$ 集合为空,算法结束。

以下图为例,计算流程展现在表格中(以-1代表无穷大,*代表顶点已确定最短路)。

dijkstra

Iter0123456
00-1-1-1-1-1-1
10*26-1-1-1-1
2 2*67-1-1-1
3 6*71722-1
4 7*172219
5 17*2219
6 2219*
7 22*

对此表稍做解释:

  • 初始只有源点0的距离已知是0,其他都是无穷大(-1)。
  • 0的邻居1和2均为被访问过,于是加入,并更新最短路距离,此轮中0的最短路距离最小,顶点0加入 $S$。
  • 由顶点1和2可以延伸到顶点3,更新3的最短路为7,此轮1的最短路距离最小,顶点1加入 $S$。
  • 以此类推,直到所有顶点加入 $S$。

练习

Leetcode 743. Network Delay Time

class Solution 
{
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) 
    {
        int INF = 1e9;
        unordered_map<int, vector<pair<int, int>>> adjvex;
        for (auto v : times) {
            adjvex[v[0]].push_back({v[1], v[2]});
        }

        vector<int> dist(n + 1, INF);
        dist[k] = 0;
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > minHeap;
        minHeap.push({0, k});
        while (!minHeap.empty()) {
            auto [d, x] = minHeap.top();
            minHeap.pop();
            if (d > dist[x] || dist[x] == INF)
                continue;
            for (auto [y, cost] : adjvex[x]) {
                if (dist[x] + cost < dist[y]) {
                    dist[y] = dist[x] + cost;
                    minHeap.push({dist[y], y});
                }
            }
        }
        int res = *max_element(dist.begin() + 1, dist.end());  
        return (res != INF ? res : -1);
    }   
};

// 作者:QRhqcDD90G
// 链接:https://leetcode-cn.com/problems/network-delay-time/solution/cpython3java-1po-su-dijkstrasuan-fa-2zui-ks36/
// 来源:力扣(LeetCode)
// 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

Bellman-Ford 算法

Bellman-Ford 可以处理有负权边的单源最短路径问题。

流程

将图 G 中的所有边,遍历 n-1 次。对于边(u,v,w),若dist[u]+w<dist[v],则更新dist[v]

  • 为什么要遍历所有边:第 i 次遍历,其实是确定其他点分别到源点的最短路径上,第 i 个顶点是谁,也可以说是经过的第 i 条边是谁。
  • 为什么要遍历 n-1 次:在每个顶点到源点的最短路径上,顶点数最多为 n 个,除非有负环,所以最多只需要遍历 n-1 次(第一个顶点已经确定下来了),就可以确定所有顶点的最短路径。

若已经经过 n-1 次遍历,再次遍历时仍有边能进行松弛,则说明图中有负权值的环路。因为此时进行松弛的路径已经包含了最少 n 条边 n + 1 个点,这说明图中一定形成了环路。去除正权值环路会使路径减小,因此在此最短路径中一定不存在正权值环路,此环路一定为负。 在完成核心算法后再次遍历尝试松弛即可检验出该图是否含有负权值环路。

下面图里有5个点8条边,需要遍历4轮。留给大家自行计算。

bellman-ford-eg

每一轮的计算过程与边的遍历顺序有关,详细过程可以参考第四篇参考文章。

练习

Leetcode 787. Cheapest Flights Within K Stops

下面是Bellman Ford结合动态规划。

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<int> dp(n, 0x3f3f3f3f);
        dp[src] = 0;
        while(1+k--){
            vector<int> next = dp;
            for(auto& x: flights) next[x[1]] = min(next[x[1]], dp[x[0]] + x[2]);
            dp = move(next);
        }
        return dp[dst] == 0x3f3f3f3f ? -1 : dp[dst];
    }
};

// 作者:MuriyaTensei
// 链接:https://leetcode-cn.com/problems/cheapest-flights-within-k-stops/solution/c-liang-chong-fang-fa-dong-tai-gui-hua-b-q8xe/
// 来源:力扣(LeetCode)
// 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

SPFA算法

介绍

SPFA算法是Shortest Path Faster Algorithm的缩写。在Bellman Ford算法中,我们有很多判断是否松弛的操作,很多时候我们并不需要那么多无用的松弛操作。我们很显然能观察到,只有上一次被松弛的结点,所连接的边,才有可能引起下一次的松弛操作。那么我们用队列来维护“哪些结点可能会引起松弛操作”,就能只访问必要的边了。

SPFA 也可以用于判断点 $S$ 是否能抵达一个负环,只需记录最短路经过了多少条边,当经过了至少 $n$ 条边时,说明点 $S$ 可以抵达一个负环。

练习

先前的 Leetcode 787. Cheapest Flights Within K Stops 可用此法。

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<int> dp(n, 0x3f3f3f3f);
        vector<vector<int> > e(n);
        queue<int> q;
        int sq;

        for(auto& x: flights) e[x[0]].push_back((x[1] << 16) + x[2]);
        dp[src] = 0;
        q.push(src);
        while(1+k-- && (sq = q.size())){
            vector<bool> vis(n);
            vector<int> cpy = dp;
            while(sq--){
                int now = q.front();
                for(auto x: e[now]){
                    int next = x>>16, v = x&0xffff;
                    cpy[next] = std::min(cpy[next], dp[now] + v);
                    if(vis[next]) continue;
                    vis[next] = 1;
                    q.push(next);
                }
                q.pop();
            }
            dp = move(cpy);
        }
        return dp[dst] == 0x3f3f3f3f ? -1 : dp[dst];
    }
};

// 作者:MuriyaTensei
// 链接:https://leetcode-cn.com/problems/cheapest-flights-within-k-stops/solution/c-liang-chong-fang-fa-dong-tai-gui-hua-b-q8xe/
// 来源:力扣(LeetCode)
// 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

Leetcode 1514. Path with Maximum Probability

class Solution {
public:
    vector<vector<pair<int, double> > > g;
    vector<double> dist;
    vector<bool> st;
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        g.resize(n);
        dist.resize(n, 0.0);
        st.resize(n, false);
        for(int i = 0; i < edges.size(); i++) {
            int x = edges[i][0], y = edges[i][1];
            double z = succProb[i];
            g[x].push_back({y, z});
            g[y].push_back({x, z});
        }
        spfa(start);
        return dist[end];
    }
    
    void spfa(int s){
        dist[s] = 1;
        queue<int> q;
        q.push(s);
        st[s] = true;
        while (!q.empty()) {
            int t = q.front();
            q.pop();
            st[t] = false;
            for (const auto &[v, w]: g[t]) {
                if (dist[v] < dist[t] * w) {
                    dist[v] = dist[t] * w;
                    if (!st[v])
                        q.push(v);
                }
            }
        }
    }
};

//作者:acvv_yaojun
//链接:https://leetcode-cn.com/problems/path-with-maximum-probability/solution/1514-gai-lu-zui-da-de-lu-jing-zui-duan-l-1ij9/
//来源:力扣(LeetCode)
//著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

Floyd 算法

介绍

Floyd 算法是用来求任意两个节点之间的最短路的多源最短路径算法,可以正确处理有向图或负权的最短路径问题,但要求最短路存在(无负环)。

Floyd 算法是一个动态规划算法,目标是求出任意节点 $i$ 到任意节点 $j$ 之间的最短距离。从动态规划的角度来说,我们需要归纳问题的子问题:从任意节点 $i$ 到任意节点 $j$ 的最短路径不外乎2种可能,一种是直接从 $i$ 到 $j$ ,另一种是从 $i$ 经过一个及以上的节点 $k$ 到 $j$ 。因此,若假设 $Dis(i,j)$ 为节点i到节点k的最短路径的距离,那么动态转移方程可以写成

$$ Dis(i, j)\ =\ \min \left( Dis(i, j),\ \min_{k} \left( Dis(i, k) + Dis(k, j) \right) \right) $$

$Dis(i, j)$ 初始化成 $i$ 和 $j$ 之间的直接距离或者无穷大。核心代码:

for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[k][j]);
        }
    }
}

练习

Leetcode 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        const int INF = 0x3f3f3f3f;
        int dist[n][n];
        memset(dist,INF,sizeof(dist));
        for(int i=0;i<n;i++)
        dist[i][i]=0;
        for(int i=0;i<edges.size();i++){
            dist[edges[i][0]][edges[i][1]]=edges[i][2];
            dist[edges[i][1]][edges[i][0]]=edges[i][2];
        }
        for(int k=0;k<n;k++){
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
                }
            }
        }
        int id=-1, minCnt=INF;
        for(int i=0;i<n;i++){
            int cnt=0;
            for(int j=0;j<n;j++){
                if(dist[i][j]<=distanceThreshold)
                    cnt++;
            }
            if(cnt<=minCnt){
                minCnt=cnt;
                id=i;
            }
        }
        return id;
    }
};

// 作者:sui-xin-yuan
// 链接:https://leetcode-cn.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/solution/zui-duan-lu-jing-mo-ban-da-ji-he-cban-fl-gs7u/
// 来源:力扣(LeetCode)
// 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

Johnson 全源最短路径算法

算法概述

任意两点间的最短路可以通过枚举起点,跑 $n$ 次 Bellman-Ford 算法解决,时间复杂度是 $O(n^2m)$ 的,也可以直接用 Floyd 算法解决,时间复杂度为 $O(n^3)$ 。

注意到堆优化的 Dijkstra 算法求单源最短路径的时间复杂度比 Bellman-Ford 更优,如果枚举起点,跑 $n$ 次 Dijkstra 算法,就可以在 $O(nm\log m)$ (本文中的 Dijkstra 采用 priority_queue 实现,下同)的时间复杂度内解决本问题,比上述跑 $n$ 次 Bellman-Ford 算法的时间复杂度更优秀,在稀疏图上也比 Floyd 算法的时间复杂度更加优秀。

但 Dijkstra 算法不能正确求解带负权边的最短路,因此我们需要对原图上的边进行预处理,确保所有边的边权均非负。

一种容易想到的方法是给所有边的边权同时加上一个正数 $x$ ,从而让所有边的边权均非负。如果新图上起点到终点的最短路经过了 $k$ 条边,则将最短路减去 $kx$ 即可得到实际最短路。

但这样的方法是错误的。考虑下图:

shortest-path

$1 \to 2$ 的最短路为 $1 \to 5 \to 3 \to 2$,长度为 -2。

但假如我们把每条边的边权加上 5 呢?

shortest-path2

新图上 $1 \to 2$ 的最短路为 $1 \to 4 \to 2$ ,已经不是实际的最短路了。

Johnson 算法则通过另外一种方法来给每条边重新标注边权。

我们新建一个虚拟节点(在这里我们就设它的编号为 0 )。从这个点向其他所有点连一条边权为 0 的边。

接下来用 Bellman-Ford 算法求出从 0 号点到其他所有点的最短路,记为 $h_i$ 。

假如存在一条从 $u$ 点到 $v$ 点,边权为 $w$ 的边,则我们将该边的边权重新设置为 $w + h_u - h_v$ 。

接下来以每个点为起点,跑 $n$ 轮 Dijkstra 算法即可求出任意两点间的最短路了。

容易看出,该算法的时间复杂度是 $O(nm \log m)$ 。

Q:那这么说,Dijkstra 也可以求出负权图(无负环)的单源最短路径了?
A:没错。但是预处理要跑一遍 Bellman-Ford,还不如直接用 Bellman-Ford 呢。

正确性证明

为什么这样重新标注边权的方式是正确的呢?

在讨论这个问题之前,我们先讨论一个物理概念——势能。

诸如重力势能,电势能这样的势能都有一个特点,势能的变化量只和起点和终点的相对位置有关,而与起点到终点所走的路径无关。

势能还有一个特点,势能的绝对值往往取决于设置的零势能点,但无论将零势能点设置在哪里,两点间势能的差值是一定的。

接下来回到正题。

在重新标记后的图上,从 $s$ 点到 $t$ 点的一条路径 $s \to p_1 \to p_2 \to \dots \to p_k \to t$ 的长度表达式如下:

$$ (w(s,p_1)+h_s-h_{p_1})+(w(p_1,p_2)+h_{p_1}-h_{p_2})+ \dots +(w(p_k,t)+h_{p_k}-h_t) $$

化简后得到:

$$ w(s,p_1)+w(p_1,p_2)+ \dots +w(p_k,t)+h_s-h_t $$

无论我们从 $s$ 到 $t$ 走的是哪一条路径, $h_s-h_t$ 的值是不变的,这正与势能的性质相吻合!

为了方便,下面我们就把 $h_i$ 称为 $i$ 点的势能。

上面的新图中 $s \to t$ 的最短路的长度表达式由两部分组成,前面的边权和为原图中 $s \to t$ 的最短路,后面则是两点间的势能差。因为两点间势能的差为定值,因此原图上 $s \to t$ 的最短路与新图上 $s \to t$ 的最短路相对应。

到这里我们的正确性证明已经解决了一半——我们证明了重新标注边权后图上的最短路径仍然是原来的最短路径。接下来我们需要证明新图中所有边的边权非负,因为在非负权图上,Dijkstra 算法能够保证得出正确的结果。

根据三角形不等式,新图上任意一边 $(u,v)$ 上两点满足: $h_v \leq h_u + w(u,v)$ 。这条边重新标记后的边权为 $w'(u,v)=w(u,v)+h_u-h_v \geq 0$ 。这样我们证明了新图上的边权均非负。

至此,我们就证明了 Johnson 算法的正确性。

参考代码

#include <cstring>
#include <iostream>
#include <queue>
#define INF 1e9
using namespace std;
struct edge {
  int v, w, next;
} e[10005];
struct node {
  int dis, id;
  bool operator<(const node& a) const { return dis > a.dis; }
  node(int d, int x) { dis = d, id = x; }
};
int head[5005], vis[5005], t[5005];
int cnt, n, m;
long long h[5005], dis[5005];
void addedge(int u, int v, int w) {
  e[++cnt].v = v;
  e[cnt].w = w;
  e[cnt].next = head[u];
  head[u] = cnt;
}
bool spfa(int s) {
  queue<int> q;
  memset(h, 63, sizeof(h));
  h[s] = 0, vis[s] = 1;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    vis[u] = 0;
    for (int i = head[u]; i; i = e[i].next) {
      int v = e[i].v;
      if (h[v] > h[u] + e[i].w) {
        h[v] = h[u] + e[i].w;
        if (!vis[v]) {
          vis[v] = 1;
          q.push(v);
          t[v]++;
          if (t[v] == n + 1) return false;
        }
      }
    }
  }
  return true;
}
void dijkstra(int s) {
  priority_queue<node> q;
  for (int i = 1; i <= n; i++) dis[i] = INF;
  memset(vis, 0, sizeof(vis));
  dis[s] = 0;
  q.push(node(0, s));
  while (!q.empty()) {
    int u = q.top().id;
    q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (int i = head[u]; i; i = e[i].next) {
      int v = e[i].v;
      if (dis[v] > dis[u] + e[i].w) {
        dis[v] = dis[u] + e[i].w;
        if (!vis[v]) q.push(node(dis[v], v));
      }
    }
  }
  return;
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    addedge(u, v, w);
  }
  for (int i = 1; i <= n; i++) addedge(0, i, 0);
  if (!spfa(0)) {
    cout << -1 << endl;
    return 0;
  }
  /*
  for(int i=1;i<=n;i++)
   cout<<h[i]<<' ';
  cout<<endl;
  */
  for (int u = 1; u <= n; u++)
    for (int i = head[u]; i; i = e[i].next) e[i].w += h[u] - h[e[i].v];
  for (int i = 1; i <= n; i++) {
    dijkstra(i);
    long long ans = 0;
    for (int j = 1; j <= n; j++) {
      if (dis[j] == INF)
        ans += j * INF;
      else
        ans += j * (dis[j] + h[j] - h[i]);
    }
    cout << ans << endl;
  }
  return 0;
}

参考

最短路 - OI Wiki (oi-wiki.org)

图文详解 Dijkstra 最短路径算法 (freecodecamp.org)

最短路径算法总结和LeetCode题目实践 / Drrany

图解:最短路径之如何理解“松弛”or“放松”?_Java_淡蓝色_InfoQ写作平台

图最短路径算法之弗洛伊德算法(Floyd) | Echo Blog (houbb.github.io)

最后修改:2022 年 08 月 22 日
如果觉得我的文章对你有用,请随意赞赏