根据这个贴: Please Share dijkstra's algorithm questions
Graph - Dijkstra's4926 views
- The Maze III
- The Maze II
- Network Delay Time
- Cheapest Flights Within K Stops
- Reachable Nodes In Subdivided Graph
- Path with Maximum Probability
- Find the City With the Smallest Number of Neighbors at a Threshold Distance
- Minimum Cost to Make at Least One Valid Path in a Grid
- Path With Minimum Effort
- Number of Restricted Paths From First to Last Node
Time complexity \(O(E \log V)\)
only use when the weight of edges is nonnegative
0. 变形题：边权为1~5
先介绍一道变形题，感觉还挺有意思的，来自 题目求助｜【求助】如何用线性时间复杂度解决单源最短路径问题(详情请看原文)
题目：
Develop a linear-time (i.e., O(m + n)-time) algorithm that solves the Single Source Shortest Path problem for graphs whose edge weights are positive integers bounded by 5. (Hint. You can either modify Dijstra’s algorithm or consider using Breath-First-Search.)
方法：贴下已经有大佬提供的思路了，我实现了一下
边权受限的话可以用桶代替 \(dijkstra\) 算法里的堆。
开一个 \(5n+1\) 大小的数组作桶，一开始把起点放入 \(0\) 号桶，之后遍历桶，碰到桶里有节点，就把节点拿出来更新与这个点相邻的点的距离，更新了的节点再放入新的桶，由于 \(dijkstra\) 算法的距离不减，因此更新的节点一定不会放到已经遍历过的桶里，复杂度 \(O(∣V∣+∣E∣)\)，是线性的。
而且上述解法对于边权很大的情况也能用，把桶的大小从原来的全是 \(1\) 调整为按指数增长即可，这个算法叫做基数堆，时间复杂度多一个 \(\log\)。
实现：
点击查看代码
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct Node
{
int v, d; //该节点的编号与距离
};
void dijkstra(vector<vector<Node>>& graph, int start, int end, vector<int>& dist) {
dist[start] = 0;
// priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int n = graph.size();
vector<int> q[5*n+1]; // 长度为5*n+1的数组，用于代替优先队列(相同最小距离的节点可能有多个)
q[0].push_back(start);
int i = 0;
while (i < 5*n+1) {
cout << "i = " << i << endl;
vector<int> us = q[i];i++;
if(us.size() == 0) continue;
// if(u == end) break;
for(int u : us) {
if(dist[u] < i-1) continue; // 之前已经求得了，但是可能出现在当前位置的列表中
dist[u] = i-1;
for(auto& node : graph[u]) {
int v = node.v, d = node.d;
if(dist[v] > dist[u] + d) {
dist[v] = dist[u] + d;
q[dist[v]].push_back(v);
}
}
for(int j = 0;j < 5*n+1;j++) {
if(q[j].size() > 0) {
for(int k = 0;k < q[j].size();k++) {
char ch = k == q[j].size()-1 ? ' ' : ',';
cout << q[j][k] << ch;
}
} else {
cout << 0 << " ";
}
}
cout << endl;
}
}
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<Node>> graph(n+1);
for(int i = 0; i < m; i++) {
int u, v, d;
cin >> u >> v >> d;
graph[u].push_back({v, d});
graph[v].push_back({u, d});
}
vector<int> dist(n+1, INT_MAX);
dijkstra(graph, 1, n, dist);
for(int i = 1; i <= n; i++) {
cout << i << ": " << dist[i] << endl;
}
// cout << dist[n] << endl;
return 0;
}
注意由于同一位置(也就是同一距离)可以对应多个节点，应该用个vector来表示桶
Leetcode 743. 网络延迟时间
题目：求有向图中的单源最短路
方法：模板题
由于所有的权重值都为非负数，所以可以考虑用dijkstra算法求解。具体思路见代码中注释。
点击查看代码
class Solution {
public:
struct Node {
int id, w;
Node(int id, int w): id(id), w(w) {}
};
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
vector<vector<Node>> graph(n+1);
for(auto& item : times) {
graph[item[0]].push_back({item[1], item[2]});
// graph[item[1]].push_back({item[0], item[2]}); // 有向图
}
vector<int> dist(n+1, INT_MAX);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
dist[k] = 0;
pq.push({0, k});
while(!pq.empty()) {
int u = pq.top().second, d = pq.top().first;
pq.pop();
if(dist[u] < d) continue; // 剪枝，已经求得更小的了
for(auto& node : graph[u]) {
int v = node.id, d = node.w;
if(dist[v] > dist[u] + d) {
dist[v] = dist[u] + d;
pq.push({dist[v], v});
}
}
}
int ans = 0;
for(int i = 1; i <= n; i++) {
ans = max(ans, dist[i]);
}
return ans == INT_MAX ? -1 : ans;
}
};
Leetcode 787. K 站中转内最便宜的航班
题目：求src到dst的最短距离，但是不能用超过K个中转点
方法：还是用最小距离做优先队列，只是节点的状态由单一的 \([id]\) 变成了 \([id, step]\)
ps：列表的写法好爽(参考 Dijkstra’s Shortest Path Algorithm / LeetCode 787. Cheapest Flights Within K Stops)
点击查看代码
class Solution {
public:
typedef tuple<int, int, int> Node;
struct Edge {
int id, w;
Edge(int id, int w): id(id), w(w) {}
};
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
vector<vector<Edge>> graph(n+1);
for(auto& flight : flights) {
graph[flight[0]].push_back({flight[1], flight[2]});
// graph[item[1]].push_back({item[0], item[2]});
}
// vector<int> d(n+1, INT_MAX);
int d[n+1][k+2]; // 记录当前最小值，用于剪枝
memset(d, 0x3f3f3f3f, sizeof(d));
priority_queue<Node, vector<Node>, greater<Node>> pq;
pq.push({0, src, 0});
while(!pq.empty()) {
auto [dist,u,step]=pq.top(); pq.pop();
bool flag = false; // 这个剪枝很重要
for(int i = 0;i <= step;i++) {
if(d[u][i] < dist) {flag = true; break;}
}
if(flag) continue;
d[u][step] = dist;
if(u == dst) return dist;
if(step >= k+1) continue;
for(auto& [v,w] : graph[u]) { // 都没用到松弛，更像是BFS了
pq.push({dist+w, v, step+1});
}
}
return -1;
}
};
还有一个DP的思路，其实就是Bellman-Ford算法
点击查看代码
class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
int dp[k+2][n];
const int INF = 0x3f3f3f3f;
memset(dp, INF, sizeof(dp));
for(int i = 0;i <= k+1;i++) dp[i][src] = 0;
for(int i = 1; i <= k+1; i++) {
for(auto& flight : flights) {
int u = flight[0], v = flight[1], w = flight[2];
dp[i][v] = min(dp[i][v], dp[i-1][u] + w);
}
}
return dp[k+1][dst] == INF ? -1 : dp[k+1][dst];
}
};
LCP 07. 传递信息
题意：求经过k轮到达某节点的方案数
方法：和上题类似，dp，不过不是求min，而是求和
点击查看代码
class Solution {
public:
int numWays(int n, vector<vector<int>>& relation, int k) {
int dp[k+1][n]; // dp[i][j] 表示经过i轮，到达j的方案数
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for(int i = 1;i <= k;i++) {
for(auto& rel : relation) {
int u = rel[0], v = rel[1];
dp[i][v] += dp[i-1][u];
}
}
return dp[k][n-1];
}
};
Leetcode 1334. 阈值距离内邻居最少的城市
题意：找到一个城市，在其距离distanceThreshold 的城市数最少
方法：由于要求所有城市之间的距离，当然是Floyd啊
点击查看代码
class Solution {
public:
int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
int d[n][n];
const int INF = 0x3f3f3f3f;
memset(d, INF, sizeof(d));
for(auto& edge : edges) {
int u = edge[0], v = edge[1], w = edge[2];
d[u][v] = d[v][u] = w;
}
for(int k = 0; k < n;k++) {
for(int i = 0;i < n;i++) {
for(int j = 0;j < n;j++) {
d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
}
}
}
int mymin = n, id;
for(int i = 0;i < n;i++) {
int cnt = 0;
for(int j = 0;j < n;j++) {
if(i != j && d[i][j] <= distanceThreshold) cnt++;
}
if(cnt <= mymin) {
mymin = cnt;
id = i;
}
}
return id;
}
};
Leetcode1368. 使网格图至少有一条有效路径的最小代价
题目：每个格子上有个数字，代表可以可以走哪个方向，你也可以修改，求达到(n,m)的最少修改次数
方法：01BFS
问题可以抽象成构建一个图，每一个方向都可以向其四个方向建边，若需要改变方向则边权是1，若不需要改变方向边权是0。然后找(0, 0)点到(n-1, m-1)的最短路。
思路就是采用0-1BFS，如果前进到下一个位置不需要代价，则插入到队首。如果前进到下一个位置需要代价，那么插入到队尾。这样就能保证整个队列是有序的。这样就不需要优先队列了。
点击查看代码
class Solution {
public:
int minCost(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size(), tot = n*m;
const int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
vector<int>dist(tot, -1);
deque<pair<int, int>>dq;
dq.push_front({0, 0});
while(!dq.empty()) {
auto p = dq.front();dq.pop_front();
int id = p.second, d = p.first;
// cout << id << " " << d << endl;
dist[id] = d;
if(id == tot-1) return d;
int x = id/m, y = id%m;
for(int i = 0;i < 4;i++) {
int xx = x+dx[i], yy = y+dy[i], id = xx*m+yy;
// cout << "xx: " << xx << " " << yy << endl;
if(xx < 0 || xx >= n || yy < 0 || yy >= m) continue;
if(dist[id] != -1) continue; // 可代替vis
if(grid[x][y] == i+1) dq.push_front({d, id});
else dq.push_back({d+1, id});
}
}
return dist[tot-1];
}
};
参考链接：