目录
前言
Dijkstra 算法是一种用于求解图中从单个源点到其他所有顶点的最短路径的经典贪心算法
核心思想
Dijkstra 算法基于 “贪心策略”：每次从尚未确定最短路径的顶点中，选择当前距离源点最近的顶点，将其标记为 “已确定最短路径”，并以该顶点为中间点，更新其相邻顶点到源点的距离。重复这一过程，直到所有顶点的最短路径都被确定。
简单来说，就是 “先找到最近的点，再用它优化其他点的距离，逐步扩大范围”。
图片来自最短路径算法之——Dijkstra算法介绍与实现 - binary220615 - 博客园。
Dijkstra 算法的实现方法有两种：
- 数组遍历：时间复杂度O (n² + m) → 适合稠密图；
- 优先队列（堆）：O (m log n) → 适合稀疏图；
边数m多的就是稠密图，边数m少的就是稀疏图，n表示顶点；
关于方法的具体实现，可见以下具体题目。
PS：本篇博客中的所有题目均来自于灵茶山艾府 - 力扣（LeetCode）分享的题单
Dijkstra经典题目
743. 网络延迟时间
使用数组解决 ：
求遍历所有节点所需要的最短时间。
- 向记录每个节点之间距离，没有相邻的节点距离设置为无穷大；
- 设置两个数组分别记录：从起始位置到各个位置需要的最短距离，那些位置已经作为起始位置扩展过了；
- 利用贪心，在记录最短路径的数组中找一个最短路的位置作为起始点开始向外进行扩展，计算向外扩展否每个位置的距离，如果该距离小于数组中记录的距离就对数组进行更新；
- 重复3操作，直到数组中已经没有能够作为起始位置的节点了。
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
//求最短路问题：Dijkstra 算法
//先使用一个二维数组记录每个位置的距离,如果两个位置之间没有联系就设置为INT_MAX
vector<vector<int>> path(n,vector<int>(n,INT_MAX/2)); //记录每个节点之间的距离
for(auto& tmp : times)
{
int x = tmp[0]-1,y = tmp[1]-1,t = tmp[2];
path[x][y]=t;
}
vector<int> vist(n); //记录k已经到过哪些位置了
vector<int> need_t(n,INT_MAX); //记录k到各个位置的最小之间
need_t[k-1]=0; //将起始位置的距离置为0
function<int()> GetNext=[&]() //计算need_t数组中的最小值,作为下一个起始位置
{
int ret = -1, t = INT_MAX;
for(int i = 0;i <n ;i++)
if(!vist[i]&& t > need_t[i]) ret=i,t = need_t[i];
return ret;
};
int point = GetNext(),clock=0;
while(point != -1)
{
clock = need_t[point]; //当前时间
vist[point] = 1;
//从point位置开始向外进行扩展
auto& nums = path[point];
for(int k = 0;k < n;k++)
need_t[k] = min(need_t[k],clock + path[point][k]);
point = GetNext();
}
int ret = 0;
for(int i = 0;i < n;i++) //计算出扩展节点需要的最大时间
ret = max(ret,need_t[i]);
return ret>=INT_MAX/2?-1:ret;
}
};使用堆解决：
- 使用优先级队列的目的在于解决每次都要遍历dis数组查找最小距离的位置，可以直接将 pair<dis[k]，k>入堆，这样在堆顶就能直接找到最小路径的位置了。
- 每次从堆顶取出最小的位置，将该位置向外进行扩展，如果扩展的距离小于dis记录的距离就对dis数据进行更新，并将该位置入堆。
- 如果这样处理，堆中必定会出现多个k值对应不同的数据，所以在取出堆顶的元素的时候要判断该堆顶对应的距离是否是最小的距离，如果不是就不需要从该位置向外进行扩展了
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
//使用堆来实现
vector<vector<int>> path(n,vector<int>(n,INT_MAX/2)); //记录每个节点之间的距离
for(auto& tmp : times)
{
int x = tmp[0]-1,y = tmp[1]-1,t = tmp[2];
path[x][y]=t;
}
vector<int> dis(n,INT_MAX); //记录k到每个位置的最小距离
//priority_queue记录最短路的位置
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
pq.push({0,k-1});
while(pq.size())
{
auto [clock,pos]=pq.top();
pq.pop();
if(clock>=dis[pos]) continue; //已经遍历过更优的位置,当前位置不需要扩展了
dis[pos]=clock;
for(int k = 0;k < n;k++) //向四周进行扩展
{
if(clock+path[pos][k]<dis[k]) //当前路径更优,加入到队列中
pq.push({clock+path[pos][k],k});
}
}
int ret=ranges::max(dis);
return ret>=INT_MAX/2?-1:ret;
}
};3341. 到达最后一个房间的最少时间 I
此题与上一题不同的是：此题是网格图而不是上面的有向加权图。所以此题的方向只有四个：上下左右。所以不需要提前存储每个位置的关系，在移动的时候直接向四个方向进行移动即可。
此题在入队的时候，会出现两种情况：
当前时间大,可以直接到下一个位置，直接使用当前时间+1；
当前时间小,不能直接到下一个位置,需要先到下一个时间，使用下一个位置的时间+1.
具体实现，见下面代码：
class Solution {
public:
int minTimeToReach(vector<vector<int>>& moveTime) {
//因为地窖是一个网格状排布,所以基本上每个房间与房间之间都有联系,所以使用堆进行处理效率更高
//使用Dijkstra 算法
//对于房间开始并可达的时间可以记作图中的边权,如果当前时间更大,这边权是1,否则边权就是moveTime[a][b]+1
int n = moveTime.size() , m = moveTime[0].size();
vector<vector<int>> dis(n,vector<int>(m,INT_MAX)); //记录到达的位置所需要的最短时间
vector<vector<int>> vist(n,vector<int>(m)); //记录已经去过的位置
priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<tuple<int,int,int>>> pq; //记录每个位置到达需要的时间,以及坐标
int dx[] = {0,0,-1,1};
int dy[] = {1,-1,0,0};
pq.push({0,0,0});
vist[0][0] = 1;
while(!pq.empty())
{
auto [clock,x,y] = pq.top();
pq.pop();
if(dis[x][y] <= clock) continue;
dis[x][y] = clock;
for(int k = 0; k < 4; k++)
{
int a = x + dx[k],b = y + dy[k];
if(a >= 0 && a < n && b >= 0 && b < m && !vist[a][b] )
{
vist[a][b] = 1;
if(clock >= moveTime[a][b] && clock + 1 < dis[a][b]) pq.push({clock+1,a,b}); //当前时间大,可以直接到下一个位置
else if(clock < moveTime[a][b] && moveTime[a][b] + 1 < dis[a][b]) pq.push({moveTime[a][b]+1 ,a,b}); //当前时间小,不能直接到下一个位置,需要先到下一个时间
}
}
}
return dis[n-1][m-1];
}
};3342. 到达最后一个房间的最少时间 II
此题是上一题的拓展，大体思路与上一题一样，只不过需要记录到达每个位置时已经走的步数，所以使用tuple<int,int,int,int>存储时间，坐标，以及步数。
class Solution {
public:
int minTimeToReach(vector<vector<int>>& moveTime) {
//因为地窖是一个网格状排布,所以基本上每个房间与房间之间都有联系,所以使用堆进行处理效率更高
//使用Dijkstra 算法
//对于房间开始并可达的时间可以记作图中的边权,如果当前时间更大,这边权是1,否则边权就是moveTime[a][b]+1
int n = moveTime.size() , m = moveTime[0].size();
vector<vector<int>> dis(n,vector<int>(m,INT_MAX)); //记录到达的位置所需要的最短时间
vector<vector<int>> vist(n,vector<int>(m)); //记录已经去过的位置
priority_queue<tuple<int,int,int,int>,vector<tuple<int,int,int,int>>,greater<tuple<int,int,int,int>>> pq; //记录每个位置到达需要的时间,以及坐标
int dx[] = {0,0,-1,1};
int dy[] = {1,-1,0,0};
pq.push({0,0,0,1});
vist[0][0] = 1;
while(!pq.empty())
{
auto [clock,x,y,step] = pq.top();
pq.pop();
if(dis[x][y] <= clock) continue;
dis[x][y] = clock;
int next = step%2==0?2:1; //计算当前步数需要花费的秒数
for(int k = 0; k < 4; k++)
{
int a = x + dx[k],b = y + dy[k];
if(a >= 0 && a < n && b >= 0 && b < m && !vist[a][b] )
{
vist[a][b] = 1;
if(clock >= moveTime[a][b] && clock + next < dis[a][b]) pq.push({clock+ next,a,b,step+1});
else if(clock < moveTime[a][b] && moveTime[a][b] + next < dis[a][b]) pq.push({moveTime[a][b]+next ,a,b,step+1});
}
}
}
return dis[n-1][m-1];
}
};3112. 访问消失节点的最少时间
此题是稀疏表所以使用堆排序进行解决。只不过此题是无向图，所以在对两个位置之间的距离进行标记的时候要标记两次。并且此题不能使用vector<vector<int>> path(n,vector<int>(n))来记录两个数之间的位置，因为n最大可以取10^5会出现内存不足。所以采用vector<vector<pair<int,int>>> path(n)来减少空间的开辟。
class Solution {
public:
vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {
//使用Dijkstra算法
//使用堆来实现
//1. 先统计每个两个位置之间的时间关系
vector<vector<pair<int,int>>> path(n);
for(auto& tmp:edges)
{
int x = tmp[0],y = tmp[1] ,t = tmp[2];
path[x].emplace_back(y,t);
path[y].emplace_back(x,t);
}
//2. 循环前的准备工作:设置最短时间数组+已经作为扩展起点的位置
vector<int> dis(n,INT_MAX/2);
vector<int> vist(n);
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq; //记录时间以及位置
vist[0] = 1;
pq.push({0,0});
while(pq.size())
{
int clock = pq.top().first,x = pq.top().second;
pq.pop();
if(dis[x] <= clock) continue;
dis[x] = clock;
vist[x] = 1;
for(auto& [next,t]: path[x])
{
if(t + clock <dis[next] && disappear[next] > t + clock && !vist[next])
pq.push({t + clock,next});
}
}
for(auto& x:dis)
if(x==INT_MAX/2) x = -1;
return dis;
}
};3604. 有向图中到达终点的最少时间
从0位置开始找到到达n-1位置的最小路径，使用Dijkstra算法来解决，因为此题是稀疏图，所以采用优先级队列来解决会更好。
注意：此题入队的实时机：
- 当时间clock >= start && clock <= end的时候可以入队列，pq.push({clock + 1 ,next})；
- 当clock < start的时候，不能直接入队列，要等一会：入队列pq.push({start + 1 ,next})。
class Solution {
public:
int minTime(int n, vector<vector<int>>& edges) {
//依旧是Dijkstra算法
//此题是稀疏图,所以使用优先级队列来实现,时间复度更小
//1. 先存储每个位置之间的关系
vector<vector<tuple<int,int,int>>> path(n); //使用tuple来存储数据,因为要存储:到达的位置,起始时间,结束时间
for(auto& nums : edges)
{
int x = nums[0], y = nums[1] ,start = nums[2] ,end = nums[3];
path[x].emplace_back(y,start,end);
}
//2. 开始准备进行循环
vector<int> dis(n,INT_MAX); //记录到达每个位置的最小时间·
vector<int> vist(n); //记录哪些位置已经作为扩展的起始位置了
priority_queue<pair<int,int> ,vector<pair<int,int>>,greater<pair<int,int>>> pq; //记录每个位置的时间
pq.push({0,0});
vist[0] = 1;
while(pq.size())
{
auto [clock,pos] = pq.top();
pq.pop();
if(dis[pos] < clock) continue;
dis[pos] = clock;
vist[pos] = 1;
for(auto& [next,start,end] : path[pos])
{
if(clock < start ) pq.push({start + 1 ,next}); //时间不够,要加时间才能入队列
else if(clock >= start && clock <= end) pq.push({clock+1 ,next}); //时间够,直接去下一个位置
}
}
return dis[n-1]==INT_MAX?-1:dis[n-1];
}
};2642. 设计可以求最短路径的图类
实现一个shortestPath，从一个节点到另一个节点的最小路径。在每个shortestPath中都使用求一次从node1到所有节点的最短路径，使用Dijkstra算法，因为是稀疏图所以采用优先级队列来实现。
class Graph {
int _n;
vector<vector<pair<int,int>>> path ; //记录每一条路径
void _addEdge(vector<int>& edge) { //设置一个统一的添加函数,让后面的函数进行复用
int pos = edge[0] ,next = edge[1] ,t = edge[2];
path[pos].emplace_back(next,t);
}
public:
Graph(int n, vector<vector<int>>& edges) {
path = vector<vector<pair<int,int>>>(n); //对path进行初始化
_n = n;
for(auto& nums: edges)
_addEdge(nums);
}
void addEdge(vector<int> _edge) {
_addEdge(_edge);
}
int shortestPath(int node1, int node2) {
//使用Dijkstra算法来解决
//因为是稀疏图所以采用优先级队列来实现
vector<int> dis(_n,INT_MAX);
vector<int> vist(_n);
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
pq.push({0,node1});
vist[node1] = 1;
while(pq.size())
{
auto [clock ,pos] = pq.top();
pq.pop();
if(clock >= dis[pos]) continue;
dis[pos] = clock;
vist[pos] = 1;
for(auto& [next,t] : path[pos])
if(clock + t < dis[next] && !vist[next]) pq.push({clock + t,next});
}
return dis[node2] ==INT_MAX? -1 : dis[node2];
}
};
/**
* Your Graph object will be instantiated and called as such:
* Graph* obj = new Graph(n, edges);
* obj->addEdge(edge);
* int param_2 = obj->shortestPath(node1,node2);
*/1514. 概率最大的路径
此题依旧是求最短路问题，只不过此题是将最短路问题进行变形，求最大概率问题。
具体代码看下方实现：
class Solution {
public:
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start_node, int end_node) {
//此题不过是将找最短路径改变成了找最大概念而已
vector<vector<pair<int,double>>> path(n); //记录每条路的情况和成功概率
//1. 先统计每条路的情况
for(int i = 0;i < edges.size() ;i++)
{
int x = edges[i][0] , y = edges[i][1];
double prob = succProb[i];
path[x].emplace_back(y,prob);
path[y].emplace_back(x,prob);
}
//2. 开始准备遍历
vector<int> vist(n); //记录以及作为起始位置的数字
vector<double> dis(n,0); //记录到达每个位置的概率
priority_queue<pair<double,int>> pq; //此时就需要使用大堆了,因为要从概率大的位置开始
pq.push({1,start_node});
vist[start_node] = 1;
while(pq.size())
{
auto [prob,pos] = pq.top();;
pq.pop();
if(dis[pos] >= prob) continue;
dis[pos] = prob;
vist[pos] = 1;
for(auto& [next,t] : path[pos])
if(t*prob > dis[next] && !vist[next]) pq.push({t*prob,next});
}
return dis[end_node] ;
}
};1631. 最小体力消耗路径
此题不建议使用BFS，因为BFS一般使用来解决最短步数的问题，而此题每个位置之间使用高度差的所以相同的步数之间有不同的高度差，所以依旧是建议使用最短路思想来解决。使用Dijkstra算法来解决，此题是网格图，就不需要建图了，直接进行循环即可，直接使用优先级队列就能找到已经走的位置中最短消耗路径。
每一次向外进行扩展都是从上下左右进行扩展的。
只不过向外进行扩展时要考虑是使用下一次的高度差，还是使用原来的高度差，要使用两者中的最大值。
class Solution {
public:
int minimumEffortPath(vector<vector<int>>& heights) {
int n = heights.size(),m = heights[0].size();
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<tuple<int,int,int>>> pq;
vector<vector<int>> dis(n,vector<int>(m,INT_MAX)); //记录每个坐标的最短路径
vector<vector<int>> vist(n,vector<int>(m)); //记录已经确定最小路径的位置
pq.push({0,0,0});
vist[0][0] = 1;
while(pq.size())
{
auto [phy,x,y] = pq.top();
pq.pop();
if(phy >= dis[x][y]) continue;
dis[x][y] = phy;
vist[x][y] = 1;
for(int k = 0 ; k < 4; k++)
{
int a = x+dx[k],b = y + dy[k];
if(a < 0 || a >= n || b < 0 ||b >= m) continue; //下一个位置越界了
int hgt = abs(heights[x][y] - heights[a][b]); //求下一个位置与当前位置的高度差
if(!vist[a][b] ) pq.push({max(hgt,phy),a,b}); //选择下一个位置和原来位置中高度差的较大值插入队列
}
}
return dis[n-1][m-1];
}
};1786. 从第一个节点出发到最后一个节点的受限路径数
此题需要找到所有受限的路径，大体上分为两步：
- 先使用Dijkstra算法，找到从n-1位置到每个位置需要的最短路径；
- 再使用DFS，从0位置开始深度优先遍历看能否在路径长度减小的情况下遍历到n-1位置；
细节：
- 此题是无向图，所以在进行路径统计的时候要统计两次；
- 因为所有路径最终都要到n-1，所以以n-1为起始位置，来查找每个位置到n-1位置的路径长度；
- 在进行DFS的时候，要进行记忆法搜索，否则会超时。
具体实现将下面代码：
class Solution {
#define MOD 1000000007
public:
int countRestrictedPaths(int n, vector<vector<int>>& edges) {
//Dijkstra + DFS
//使用Dijkstra算法求出从n-1位置开始到每个位置的最短路路径
//再使用DFS从0位置开始找路径长度依次递减并且能到n-1位置的路径个数
//使用Dijkstra算法
vector<vector<pair<int,int>>> path(n); //记录每个位置之间的路径关系
for(auto& nums: edges)
{
int x = nums[0] - 1 , y = nums[1] - 1 ,t = nums[2];
path[x].emplace_back(y,t);
path[y].emplace_back(x,t);
}
vector<int> dis(n,INT_MAX);
vector<int> vist(n);
priority_queue<pair<int,int> ,vector<pair<int,int>>,greater<pair<int,int>>> pq;
pq.push({0,n-1});
vist[n-1] = 0;
while(pq.size())
{
auto [clock,pos] = pq.top();
pq.pop();
if(dis[pos] <= clock) continue;
vist[pos] = 1;
dis[pos] = clock;
for(auto& [next,t] : path[pos])
if(clock + t <dis[next] && !vist[next]) pq.push({clock + t,next});
}
//使用DFS找路径
vector<int> have_go(n);
vector<int> each_pos(n,-1); //存储已经到的位置的路径长度
function<int(int,vector<int>&)> dfs = [&](int pos,vector<int>& hg) //进行DFS,其中hg表示当前路径已经遍历过的位置
{
if(pos == n-1) return 1;
if(each_pos[pos] != -1) return each_pos[pos];
int ret = 0;
for(auto& [next,_] : path[pos])
{
if(!hg[pos] &&dis[next] < dis[pos])
{
hg[pos] = 1;
ret = (ret + dfs(next,hg)%MOD)%MOD;
hg[pos] = 0;
}
}
each_pos[pos] = ret;
return ret;
};
return dfs(0,have_go);
}
};总结
对于求最小路径的题目一般套路都是固定的，两种方法：数组或优先级队列。关于该类题目最重要的就是考虑何时入队列。