您现在的位置是:首页 >其他 >最短路径算法-Dijkstra网站首页其他
最短路径算法-Dijkstra
简介最短路径算法-Dijkstra
使用 Dijkstra 算法的前提,加权有向图,没有负权重边,求最短路径
用到了优先级队列处理数据 => 贪心思想
其实对于dijkstra算法的理解不能认为就是求最小值的算法 => 最优化算法(最大值也可以)
标准 Dijkstra 算法是计算最短路径的,但你有想过为什么 Dijkstra 算法不允许存在负权重边么?
因为 Dijkstra 计算最短路径的正确性依赖一个前提:路径中每增加一条边,路径的总权重就会增加。
这个前提的数学证明大家有兴趣可以自己搜索一下,我这里只说结论,其实你把这个结论反过来也是 OK 的:
如果你想计算最长路径,路径中每增加一条边,路径的总权重就会减少,要是能够满足这个条件,也可以用 Dijkstra 算法。
vector<int> dijkstra(int start, vector<vector<pair<int, int>>>& graph, int n) {
vector<int> distTo(n + 1, INT_MAX);
distTo[start] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > pq;
pq.emplace(0, start);
while(!pq.empty()) {
auto [curDistFromStart, curNodeID] = pq.top();
pq.pop();
if(curDistFromStart > distTo[curNodeID]) continue;
for(auto& [nextNodeID, weight]: graph[curNodeID]) {
int distToNextNode = distTo[curNodeID] + weight;
if(distTo[nextNodeID] > distToNextNode) {
distTo[nextNodeID] = distToNextNode;
pq.emplace(distToNextNode, nextNodeID);
}
}
}
return distTo;
}
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
vector<vector<pair<int, int>>> graph(n + 1);
for(int i = 1; i <= n; i++) {
graph[i] = vector<pair<int, int>>();
}
for(auto& edge: times) {
int from = edge[0], to = edge[1], weight = edge[2];
graph[from].emplace_back(to, weight);
}
vector<int> distTo = dijkstra(k, graph, n);
// 找到最长的那一条最短路径
int res = 0;
for(int i = 1; i < distTo.size(); i++) {
if(distTo[i] == INT_MAX) return -1;
res = max(res, distTo[i]);
}
return res;
}
private:
vector<int> dijkstra(int start, vector<vector<pair<int, int>>>& graph, int n) {
vector<int> distTo(n + 1, INT_MAX);
distTo[start] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > pq;
pq.emplace(0, start);
while(!pq.empty()) {
auto [curDistFromStart, curNodeID] = pq.top();
pq.pop();
if(curDistFromStart > distTo[curNodeID]) continue;
for(auto& [nextNodeID, weight]: graph[curNodeID]) {
int distToNextNode = distTo[curNodeID] + weight;
if(distTo[nextNodeID] > distToNextNode) {
distTo[nextNodeID] = distToNextNode;
pq.emplace(distToNextNode, nextNodeID);
}
}
}
return distTo;
}
};
这题还有一个难点就是抽象出图
class Solution {
public:
int minimumEffortPath(vector<vector<int>>& heights) {
int m = heights.size(), n = heights[0].size();
// 定义:从(0,0)到(i,j)的最小体力消耗是effortTo[i][j]
vector<vector<int>> effortTo(m, vector<int>(n, INT_MAX));
effortTo[0][0] = 0;
auto tupleCmp = [](const auto& e1, const auto& e2) {
auto&& [x1, y1, d1] = e1;
auto&& [x2, y2, d2] = e2;
return d1 > d2;
};
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, decltype(tupleCmp) > pq(tupleCmp);
pq.push(tuple(0, 0, 0));
while(!pq.empty()) {
auto [curX, curY, curEffort] = pq.top();
pq.pop();
if(curX == m - 1 && curY == n - 1) return curEffort;
if(curEffort > effortTo[curX][curY]) continue;
for(auto& neighbor: adjacent(heights, curX, curY)) {
int nextX = neighbor[0];
int nextY = neighbor[1];
int effortToNextNode = max(effortTo[curX][curY], abs(heights[curX][curY] - heights[nextX][nextY]));
if(effortTo[nextX][nextY] > effortToNextNode) {
effortTo[nextX][nextY] = effortToNextNode;
pq.push(tuple(nextX, nextY, effortToNextNode));
}
}
}
return -1;
}
private:
vector<vector<int>> dirs{{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
vector<vector<int>> adjacent(vector<vector<int>>& matrix, int x, int y) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> neighbors;
for(auto& dir: dirs) {
int nx = x + dir[0];
int ny = y + dir[1];
if(nx >= m || nx < 0 || ny >= n || ny < 0) continue;
neighbors.push_back({nx, ny});
}
return neighbors;
}
};
class Solution {
public:
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
vector<vector<pair<double, int>>> graph(n);
for(int i = 0; i < edges.size(); i++) {
int from = edges[i][0];
int to = edges[i][1];
double weight = succProb[i];
// 无向图 == 双向图
graph[from].emplace_back(weight, to);
graph[to].emplace_back(weight, from);
}
return dijkstra(start, end, graph);
}
double dijkstra(int start, int end, vector<vector<pair<double, int>>> graph) {
int n = graph.size();
vector<double> probTo(n, );
probTo[start] = 1;
priority_queue<pair<int, double> > pq;
pq.emplace(start, 1);
while(!pq.empty()) {
auto [curNodeID, curProbFromStart] = pq.top();
pq.pop();
if(curNodeID == end) return curProbFromStart;
if(curProbFromStart < probTo[curNodeID]) continue;
for(auto& neighbor: graph[curNodeID]) {
int nextNodeID = neighbor.second;
double probToNextNode = probTo[curNodeID] * neighbor.first;
if(probTo[nextNodeID] < probToNextNode) {
probTo[nextNodeID] = probToNextNode;
pq.emplace(nextNodeID, probToNextNode);
}
}
}
return 0.0;
}
};
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。