最短路径算法总结和LeetCode题目实践
本文最后更新于：2021年2月10日 上午
常见的最短路径算法总结。
最短路径算法总结和 LeetCode 题目实践
最近复习到了图相关，总结了最短路径问题的几个常用算法（Dijsktra 算法、Floyd 算法、Bellman-Ford 算法、SPFA 算法）。给出了具体题目实现。
给定图 G(V,E)，共有 n 个顶点：
Dijsktra 算法
通常用于计算单源最短路径问题，即给定源点src，计算其他每个顶点到源点的最短距离。（注意：Dijsktra 不能解决边权有负值的情况）
基本思想：设置一个顶点集合 S，存放已找到最短路径的顶点，每次从 V-S 集合中找距离源点距离最小的点，假设为u，将其加入集合 S。再次遍历 V-S 集合中的点，设为v，看是否能对边(u,v)进行松弛操作(dist[u]+G[u][v]<dist[v])。
伪代码：
// 设置的数据结构：
bool visited[n]; // visited[i]=true表示顶点i已经加入集合S
int dist[n]; // dist[i]表示顶点i距离源点的最短距离
int pre[n]; // 到达pre[i]的最短路径上，i的前一个顶点
遍历n次：
找出V-S中距离源点最近的点，记为u
若不存在，说明G不是连通图
visited[u]=true
遍历V-S中所有点v
若dist[u]+G[u][v]<dist[v]：
更新dist[v]和pre[v]例：
-
思路：计算源点到其他所有点所需的时间，记录在数组 dist[]中，返回 dist[]中的最大值，即延迟时间
class Solution { public: int networkDelayTime(vector<vector<int>> ×, int n, int k) { // 将times转换为邻接矩阵G vector<vector<int>> G(n + 1, vector<int>(n + 1, INT32_MAX)); int len = times.size(), ui, vi, wi; for (int i = 0; i < len; ++i) { ui = times[i][0], vi = times[i][1], wi = times[i][2]; G[ui][vi] = wi; } vector<int> dist(n + 1, INT32_MAX); // 到源点的距离 vector<int> visited(n + 1, false); // 是否加入集合S dist[k] = 0; for (int i = 0; i < n; ++i) { // 遍历n次 // 找出集合V-S中距离源点最近的 int u = -1, minDist = INT32_MAX; for (int j = 1; j <= n; ++j) { if (!visited[j] && dist[j] < minDist) { u = j; minDist = dist[j]; } } if (u == -1) return -1; // 若未找到，返回-1 visited[u] = true; // 将u加入集合S // 用顶点u更新V-S中其他顶点的最短距离 for (int v = 1; v <= n; ++v) { if (!visited[v] && G[u][v] != INT32_MAX) dist[v] = min(dist[v], dist[u] + G[u][v]); } } return *max_element(dist.begin() + 1, dist.end()); } };
-
思路：使用优先队列+Dijsktra 算法。记录到达每个结点(城市)处的中转次数和花费，优先操作花费最少的结点。
class City { public: int index; // 城市编号 int cost; // 花费 int hop; // 到达该城市的中转次数 City(int i, int c, int h) { index = i, cost = c, hop = h; } friend bool operator<(const City &a, const City &b) { return a.cost > b.cost; } }; class Solution { public: int findCheapestPrice(int n, vector<vector<int>> &flights, int src, int dst, int K) { // 将flights转换为邻接矩阵 vector<vector<int>> G(n, vector<int>(n, INT32_MAX)); int len = flights.size(), ui, vi, wi; for (int i = 0; i < len; ++i) { ui = flights[i][0], vi = flights[i][1], wi = flights[i][2]; G[ui][vi] = wi; } // 创建优先队列，花费少的结点优先 priority_queue<City> pq; pq.push(City(src, 0, 0)); while (!pq.empty()) { City t = pq.top(); pq.pop(); if (t.hop > K + 1) // k站中转，hop最大可以等于K+1 continue; int u = t.index, c = t.cost, h = t.hop; if (u == dst) // 若能到达目的地，则一定是最优花费的 return c; for (int v = 0; v < n; ++v) { if (G[u][v] != INT32_MAX) pq.push(City(v, G[u][v] + c, h + 1)); } } return -1; } };
Dijsktra 算法+DFS
上面两道题都没有要求输出具体的最短路径，所以没有使用 pre 数组。有两种稍微复杂的情况如下：
- 源点到某个点的最短路径不止一条
- 不光要求从源点到其他点的距离最短，还有其他最优要求（e.g. 每个点有一个属性值，要求总属性值最大/小）
第一个问题可以通过将 pre 数组修改为vector<vecotr<int> >pre，然后对pre进行 DFS 得到每条路径。
第二个问题，如果最优要求比较简单，可以直接在原有 Dijsktra 算法上修改，如果比较麻烦，可以先求出所有最短路径，再通过 DFS 对每条路径的属性进行比较，得到要求解。
思路：该题中不仅要求距离最短，还要求所有最短路径中，输出救援队人数最多的那条（也就是路径经过的所有城市点权相加）
#include <bits/stdc++.h> using namespace std; int maxSum = 0; int ansNum = 0; vector<int> curPath; void dfs(vector<vector<int>> pre, vector<int> w, int u, int src) { if (u == src) { ansNum++; curPath.push_back(u); // 计算救援队总人数 int len = curPath.size(), curSum = 0; for (int i = 0; i < len; ++i) curSum += w[curPath[i]]; maxSum = max(maxSum, curSum); curPath.pop_back(); return; } curPath.push_back(u); vector<int> last = pre[u]; for (int i = 0; i < last.size(); ++i) dfs(pre, w, last[i], src); curPath.pop_back(); } int main() { int n, m, src, dst; cin >> n >> m >> src >> dst; vector<int> w(n); // 每个城市的救援队人数 vector<vector<int>> G(n, vector<int>(n, INT32_MAX)); for (int i = 0; i < n; ++i) cin >> w[i]; int ui, vi, wi; for (int i = 0; i < m; ++i) { cin >> ui >> vi >> wi; G[ui][vi] = G[vi][ui] = wi; } // 先单纯使用Dijsktra算法计算出所有最短路径 vector<int> dist(n, INT32_MAX); vector<bool> visited(n, false); vector<vector<int>> pre(n, vector<int>()); dist[src] = 0; for (int i = 0; i < n; ++i) { int u = -1, minDist = INT32_MAX; for (int j = 0; j < n; ++j) { if (!visited[j] && dist[j] < minDist) { u = j; minDist = dist[j]; } } if (u == -1) return 0; visited[u] = true; for (int v = 0; v < n; ++v) { if (!visited[v] && G[u][v] != INT32_MAX) { int tmp = G[u][v] + dist[u]; if (tmp < dist[v]) { // 更新最短路径 dist[v] = tmp; pre[v].clear(); pre[v].push_back(u); } else if (tmp == dist[v]) pre[v].push_back(u); } } } // DFS得到最短路径条数和救援队最大人数 dfs(pre, w, dst, src); cout << ansNum << " " << maxSum; }
Floyd 算法
Floyd 算法可以用来解决多源最短路径问题，它会计算图中每两个点之间的最短路径。
基本思想：如果令 k 作为顶点 i 和 j 之间路径的中介点能够得到一条更短的路径，则令 k 作为其最短路径的中介点。
伪代码：(由伪代码可知 Floyd 算法的复杂度为 $O(n^3)$ ，所以通常用于图点数不太大的情况)
// dist[i][j]表示顶点i和j之间的最短距离
for k in (1,n): // 令每个点分别作为中介点进行测试
for i in (1,n):
for j in (1,n):
if dist[i][j]>dist[i][k]+dist[k][j]:
dist[i][j]=dist[i][k]+dist[k][j]- 注意一下这里的 k，也就是枚举的中介点必须在最外层才能保证这个贪心的正确性。因为 Floyd 算法的本质是 DP，也就是说
dist[k][i][j]=min(dist[k-1][i][j],dist[k-1][i][k]+dist[k-1][k][j])，如果 k 不在最外层就不能保证当计算到 k 时，所有 k-1 的值都是最优的。
例： LeetCode-1334. 阈值距离内邻居最少的城市
思想：用 Floyd 算法计算出每两个城市之间的最短距离，然后分别遍历每个城市，计算满足要求的邻居数量，返回邻居最少的城市。
class Solution { public: int findTheCity(int n, vector<vector<int>> &edges, int distanceThreshold) { // 初始化邻接矩阵，也作为距离矩阵dist vector<vector<int>> dist(n, vector<int>(n, INT32_MAX)); int len = edges.size(), ui, vi, wi; for (int i = 0; i < len; ++i) { ui = edges[i][0], vi = edges[i][1], wi = edges[i][2]; dist[ui][vi] = dist[vi][ui] = wi; } for (int i = 0; i < n; ++i) // 将到自身的距离初始化为0，下面的遍历中就不需要对kij三个点中有相等情况时的特殊处理 dist[i][i] = 0; for (int k = 0; k < n; ++k) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (dist[i][k] < INT32_MAX && dist[k][j] < INT32_MAX && (dist[i][k] + dist[k][j] < dist[i][j])) dist[i][j] = dist[i][k] + dist[k][j]; } } } // 找出满足条件邻居最少的城市 int ansCity, ansNum = INT32_MAX; for (int i = 0; i < n; ++i) { int tmpNum = 0; for (int j = 0; j < n; ++j) { if (dist[i][j] <= distanceThreshold) tmpNum++; } if (tmpNum <= ansNum) { ansNum = tmpNum; ansCity = i; } } return ansCity; } };
Bellman-Ford 算法
Bellman-Ford 算法也是解决单源最短路径，其还可以处理有负边权的图。
首先要明确一点，在带有负边权的图中，不能有源点可达的负环，否则当从源点出发，将该负环循环走无数次，路径值会越来越小，也就不存在最短路径。所以当图中存在从源点可达的负环时，函数要返回 false。
思路：将图 G 中的所有边，遍历 n-1 次。对于边(u,v,w)，若dist[u]+w<dist[v]，则更新dist[v]。
- 为什么要遍历所有边：第 i 次遍历，其实是确定其他点分别到源点的最短路径上，第 i 个顶点是谁，也可以说是经过的第 i 条边是谁。
- 为什么要遍历 n-1 次：在每个顶点到源点的最短路径上，顶点数最多为 n 个，除非有负环，所以最多只需要遍历 n-1 次(第一个顶点已经确定下来了)，就可以确定所有顶点的最短路径。
伪代码：
遍历n-1次：
对每条边(u,v,w)：
dist[v]=min(dist[v],dist[u]+w)
// 再遍历一次判断是否存在负环
对每条边(u,v,w)：
if dist[u]+w<dist[v]: // 若数组中还有未达到最优的值，只能说明图中有负环，返回false
return false;- 在某次遍历中，如果所有的 dist 值都没有被优化，说明 dist 中所有值已经达到最优，可以直接退出循环。
- 如果要记录最短路径，可以设置一个
set<int> pre，因为每次遍历会反复访问重复的点，而 set 可以自行去重。
例：
-
class Solution { public: int findCheapestPrice(int n, vector<vector<int>> &flights, int src, int dst, int K) { vector<int> dist(n, INT32_MAX); dist[src] = 0; int len = flights.size(); vector<int> copy(dist); for (int i = 0; i < K + 1; ++i) { // K次中转，可以经过K+1条边 for (int j = 0; j < len; ++j) { // 遍历每条边 int u = flights[j][0], v = flights[j][1], w = flights[j][2]; if (dist[u] < INT32_MAX) copy[v] = min(copy[v], dist[u] + w); // 更新在copy上是为了防止在一次遍历中多次修改dist[i]的值，则其不止确定了一条边 } dist = copy; } return dist[dst] == INT32_MAX ? -1 : dist[dst]; } }; -
思路：这题咋一看有点唬人，其实也满足贪心策略，因为他要找的是最大相乘边权路径，而每个边权大小 ∈[0,1]，随着路径上边数的增加，边权只会越来越小，所以用 Bellman-Ford 算法时，最先得到的最大路径一定是最优解。
class Solution { public: double maxProbability(int n, vector<vector<int>> &edges, vector<double> &succProb, int start, int end) { int len = edges.size(); vector<double> prob(n, 0); prob[start] = 1.0; for (int i = 0; i < n - 1; ++i) { bool isChange = false; for (int j = 0; j < len; ++j) { int u = edges[j][0], v = edges[j][1]; double w = succProb[j]; if (prob[u] * w > prob[v]) { prob[v] = prob[u] * w; isChange = true; } if (prob[v] * w > prob[u]) { prob[u] = prob[v] * w; isChange = true; } } if (!isChange) break; } return prob[end]; } };
SPFA 算法
SPFA 算法是基于 Bellman-Ford 算法改进得到的。B-F 算法每次边遍历，要对所有边都进行一次操作，但其实哪些边需要进行操作是可以提前确定的：只有当某个顶点 u 的 dist[u]值改变时，从他出发的边(u,v)才需要进行操作，因为只有此时顶点 v 的值才可能改变。
基本操作：使用队列来存储 dist 值改变的点。每次取队首的顶点，然后对该顶点的所有边进行操作，如果边的另一个顶点的 dist 值改变，则将该顶点加入到队列中（如果该顶点当前不在队列中）。这样一直到队列为空。
- 如果图中存在从源点可达的负环，则可能存在顶点无限次入队，使得队列不可能为空，这时用一个数组来记录每个顶点的入队次数，当一个顶点入队次数超过 n-1 时，返回 false。
伪代码：
vector<bool> in; // 标记顶点是否在队列中
vector<int> count; // 记录顶点的入队次数
queue<int> q;
q.push(src); // 源点入队
while(!q.empty()){
int u = q.pop();
in[u] = false;
对u的每条边进行松弛操作：
若v的dist值改变且!in[v]：
q.push(v);
count[v]++;
in[v] = true;
if count[v]>n-1:
return false;
}例：
-
思路：每个结点处添加颜色信息，以实现交替查找不同颜色的边。由于每个点可能多次访问，但是边不能重复访问，所以设置一个边访问表来记录边的访问情况。只要当前边没有访问过，就可以新建结点入队，这样保证了能得到所有解。
class Node { public: int color; // 0表示由一条红边到该点，1表示由一条蓝边到该点 int vertex; // 顶点编号 int len; // 长度 Node(int c, int v, int l) { color = c; vertex = v; len = l; } }; class Solution { public: vector<int> shortestAlternatingPaths(int n, vector<vector<int>> &red_edges, vector<vector<int>> &blue_edges) { // 建立邻接表和边访问表 vector<vector<int>> redAdj(n, vector<int>()), blueAdj(n, vector<int>()); vector<vector<bool>> redVis(n, vector<bool>()), blueVis(n, vector<bool>()); int redNum = red_edges.size(), blueNum = blue_edges.size(); for (int i = 0; i < redNum; ++i) { redAdj[red_edges[i][0]].push_back(red_edges[i][1]); redVis[red_edges[i][0]].push_back(false); } for (int i = 0; i < blueNum; ++i) { blueAdj[blue_edges[i][0]].push_back(blue_edges[i][1]); blueVis[blue_edges[i][0]].push_back(false); } vector<int> ans(n, INT32_MAX); queue<Node> q; q.push(Node(1, 0, 0)); q.push(Node(0, 0, 0)); ans[0] = 0; while (!q.empty()) { Node u = q.front(); q.pop(); if (u.color == 1) { // 若u由一条蓝边到，找从u出发的红边 vector<int> nextRed = redAdj[u.vertex]; for (int i = 0; i < nextRed.size(); ++i) { int v = nextRed[i]; // 若该边未访问过，将结点入队 if (!redVis[u.vertex][i]) { redVis[u.vertex][i] = true; q.push(Node(0, v, u.len + 1)); ans[v] = min(ans[v], u.len + 1); } } } else { vector<int> nextBlue = blueAdj[u.vertex]; for (int i = 0; i < nextBlue.size(); ++i) { int v = nextBlue[i]; if (!blueVis[u.vertex][i]) { blueVis[u.vertex][i] = true; q.push(Node(1, v, u.len + 1)); ans[v] = min(ans[v], u.len + 1); } } } } for (int i = 1; i < n; ++i) ans[i] = (ans[i] == INT32_MAX) ? -1 : ans[i]; return ans; } };
-
struct Edge { int v; int w; Edge(int iv, int iw) { v = iv; w = iw; } }; struct Node { int v; int w; int k; Node(int iv, int iw, int ik) { v = iv, w = iw, k = ik; } }; class Solution { public: int findCheapestPrice(int n, vector<vector<int>> &flights, int src, int dst, int K) { // 初始化邻接表 vector<vector<Edge>> adj(n, vector<Edge>()); for (const auto &edge:flights) adj[edge[0]].push_back(Edge(edge[1], edge[2])); vector<int> res(n, INT32_MAX); res[src] = 0; queue<Node> q; q.push(Node(src, 0, 0)); while (!q.empty()) { Node t = q.front(); q.pop(); if (t.k > K + 1) continue; vector<Edge> next = adj[t.v]; for (const auto &tmp : next) { int w = tmp.w + t.w; if (w < res[tmp.v]) { res[tmp.v] = w; q.push(Node(tmp.v, w, t.k + 1)); } } } return res[dst] == INT32_MAX ? -1 : res[dst]; } };
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！