Dijkstra算法详解：从原理到LeetCode实战
Dijkstra算法详解：从原理到LeetCode实战
Dijkstra算法是解决单源最短路径问题的经典算法，广泛应用于网络路由、地图导航等领域。本文将从原理、实现到具体应用，全面解析Dijkstra算法，并通过LeetCode 743题"网络延迟时间"进行实战演练。
原理介绍
寻找最短路径
Dijkstra算法的主要思想是贪心，每次将选中距离源点最近的点，并不断更新。为实现这个目的，我们维护一个dist[]数组和一个visited[]数组，并规定：
- 图的邻接矩阵中，若a无指向b的边，将其距离视为∞(为显示直观并且防止溢出，可设为MAX=INT_MAX/2)
- dist[i]数组表示目前更新到的i位置距离源点的最短距离。
- visited[i]==1表示i到源点的距离已是最近，无法再更新。
我们进行以下步骤：
- 初始化邻接矩阵、dist数组和visited数组
- 扫描dist数组，找出距离源点最近的节点i（若visited[i]=1，该节点不进行比较）
- i距离源点的最短距离已被找到，将visited[i]设为1
- 找出i指向的节点并更新他们与源点的最短距离。
- 重复2~4
请看下面这个例子：
设源点为A，初始化阶段把源点dist[0]初始化为0，其余为MAX。(源点到源点的最短距离为0，其他点还未扫描到，可暂时用MAX初始化。同时，在扫描结束后，也可以依据是否有节点距离源点MAX，判断该有向图是否存在无法到达的节点。)
节点 A B C D E F
dist 0 MAX MAX MAX MAX MAX
visited 0 0 0 0 0 0
（1）第一次扫描：
扫描dist数组，距离源点最近的节点为A，因此A到源点的最短距离为0。
将visited[ A ]设为1。
将其余点设为min (dist[ A ]+G[ A ][i] ,dist[i])
(A到源点的最短距离已经求出，更新A直接指向的点i到源点的距离，即dist[A]+G[A][i]，该点有可能比原本的dist[i]大，取最小)
节点 A B C D E F
dist 0 1 5 MAX MAX MAX
visited 1 0 0 0 0 0
（2）第二次扫描：
扫描dist数组，与源点距离最近的点为B（注意:visited[A]已被设为1，表示已找到最短距离无法再更新，因此A不被扫描到。）
将visited[ B ]设为1。
将其余点设为min (dist[ B ]+G[ B ][i] ,dist[i])
这里dist[C]的值被更新，因为A->B->C的距离比A->C的距离短。
节点 A B C D E F
dist 0 1 4 3 MAX MAX
visited 1 1 0 0 0 0
（3）第三次扫描
扫描dist数组，与源点距离最近的点为D（注意:visited[i]已被设为1，表示已找到最短距离无法再更新，因此i不被扫描到。）
将visited[ D ]设为1。
将其余点设为min (dist[ D ]+G[ D ][i] ,dist[i])
节点 A B C D E F
dist 0 1 4 3 4 7
visited 1 1 0 1 0 0
（4）第四次扫描
扫描dist数组，与源点距离最近的点为E（注意:visited[i]已被设为1，表示已找到最短距离无法再更新，因此i不被扫描到。）
将visited[ E ]设为1。
将其余点设为min (dist[ E ]+G[ E ][i] ,dist[i])
节点 A B C D E F
dist 0 1 4 3 4 7
visited 1 1 0 1 1 0
（5）第五次扫描
扫描dist数组，与源点距离最近的点为C（注意:visited[i]已被设为1，表示已找到最短距离无法再更新，因此i不被扫描到。）
将visited[ C ]设为1。
将其余点设为min (dist[ C ]+G[ C ][i] ,dist[i])
节点 A B C D E F
dist 0 1 4 3 4 7
visited 1 1 1 1 1 0
（6）第六次扫描
扫描dist数组，与源点距离最近的点为F（注意:visited[i]已被设为1，表示已找到最短距离无法再更新，因此i不被扫描到。）
将visited[ F ]设为1。
将其余点设为min (dist[ F ]+G[ F ][i] ,dist[i])
节点 A B C D E F
dist 0 1 4 3 4 7
visited 1 1 1 1 1 1
（7）第七次扫描
所有visited均被设为1，表示所有节点均已找到与源点的最短距离。
特殊情况
若有向图中有的节点无法到达：
节点 A B C D E F G
dist 0 1 4 3 4 7 MAX
visited 1 1 1 1 1 1 0
此时我们已经把能到达的点的最短路径找出来了，按之前的步骤扫描dist数组，发现距离源点最近的节点为G，（前面已经说过了，visited数组限制了A~F不进行此次扫描的比较）。而dist[G]的值为MAX，即我们初始化的“无限大”，因此判断存在无法到达的节点。
例题
题目
有 n 个网络节点，标记为 1 到 n。
给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。
现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。
示例
示例1：
输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2
示例 2：
输入：times = [[1,2,1]], n = 2, k = 1
输出：1
示例 3：
输入：times = [[1,2,1]], n = 2, k = 2
输出：-1
题目来源于：743. 网络延迟时间 - 力扣（LeetCode）
Code
朴素的Dijkstra算法
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
const int MAX=INT_MAX/2;
vector<vector<int>>g(n,vector<int>(n,MAX)); ///邻接矩阵
for(auto x:times){
g[x[0]-1][x[1]-1]=x[2];
}
vector<int>dist(n,MAX); ///记录各点到源点的最短路径
vector<int>visit(n);
dist[k-1]=0;
while(1){
int x=-1;
for(int i=0;i<n;i++){
if(!visit[i]&&(x<0||dist[i]<dist[x])){
x=i;
}
}
if(x<0){ ///dist填满，返回最大值
int ans=0;
for(int i=0;i<n;i++){
ans=max(ans,dist[i]);
}
return ans;
}
if(dist[x]==MAX)return -1;
visit[x]=1;
for(int y=0;y<n;y++){
dist[y]=min(dist[y],dist[x]+g[x][y]);
}
}///while
return -1;
}
堆优化
在前面的代码中，有一步需要遍历dist数组，找出最短距离的点。我们可以用一个优先队列来进行优化，每次从队列中取出的节点就是所需要的点
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
vector<vector<pair<int,int>>>g(n); ///邻接矩阵
for(auto x:times){
g[x[0]-1].emplace_back(x[1]-1,x[2]);
}
vector<int>dist(n,INT_MAX); ///记录各点到源点的最短路径
dist[k-1]=0;
auto cmp=[&](auto x,auto y){
return x.second>y.second;
};
priority_queue<pair<int,int>,vector<pair<int,int>>,decltype(cmp)> pq(cmp);
pq.emplace(k-1,0);
while(!pq.empty()){
auto [x,dx]=pq.top();
pq.pop();
if(dx>dist[x])continue;
for(auto [y,d]:g[x]){
if(dx+d<dist[y]){
dist[y]=dx+d;
pq.emplace(y,dx+d);
}
}
}///while
int mx=0;
for(int i=0;i<n;i++){mx=max(mx,dist[i]);}
return mx==INT_MAX?-1:mx;
}