算法描述
该算法维护了两个点集，S和V。其中S集合为已经确定到源点最短路径的点集，V集合为未确定到源点最短路径的点集。
循环进行以下操作直到所有点都确定了与源点的最短路径：从V集合中取出一点，使得该点到源点距离为V集合中最短。然后通过该点，更新与该点相连的点距离源点的距离。最后，将该点放入S集合中。
算法正确性
该算法最关键的步骤就是从V集合中取点的操作。设i为V集合中一点，j为V集合中任意其他一点，dis[i]<dis[j]，则dis[i]<dis[j]+a[j][i]，故点i距离源点距离为确定值。其中dis[i]为源点到点i的最短路径，a[j][i]为点j到点i的距离。
由于我们需要取一个已经确定了与源点最短路径的点，如果取出的点的dis[i]并不是最小的，那么其他点是可以更新该点的，也就是说该点距离源点的最短路径并不是确定的。相反，如果dis[i]小于集合V中的任何其他点到源点的距离，那么集合V中的其他点一定不能更新dis[i]使dis[i]更小，则点v距离源点的距离dis[i]一定是确定的。
一些不足
首先，dijkstra算法得以成立的前提是从V集合中取出的点距离源点的最短路是确定的，不会因为后续的更新而变化的，但是如果图存在负权，则dis[i]<dis[j],但dis[i]不一定小于dis[j]+a[j][i]，这时选择的i点距离源点的最短路就不是确定的了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| const int N = 1e5 + 10;
int h[N],cnt = 0;
struct node{
int w,v,next;
}a[N];
void add(int u,int v,int w){
a[++cnt].w = w;
a[cnt].v = v;
a[cnt].next = h[u];
h[u] = cnt;
}
int n,m;
int dis[N],vis[N];
void dijkstra(){
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[1] = 0;
for(int i = 0;i<n;i++){
int u = 0;
for(int j = 1;j<=n;j++){
if(!vis[j]&&dis[j]<dis[u]) u = j;
}
vis[u] = 1;
for(int j = h[u];j;j = a[j].next){
int v = a[j].v,w = a[j].w;
dis[v] = min(dis[v],dis[u]+w);
}
}
}
|
优先队列（二叉堆）优化
朴素算法中如果想从集合V中选点需要$O(n)$的时间复杂度，但是如果使用优先队列可以将这一步骤优化到$O(logn)$。直接上代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| const int N = 1e5 + 10;
int h[N],cnt = 0;
struct node{
int w,v,next;
}a[N];
void add(int u,int v,int w){
a[++cnt].w = w;
a[cnt].v = v;
a[cnt].next = h[u];
h[u] = cnt;
}
priority_queue<pair<int,int>> q;
int n,m,u,v,w;
int dis[N],vis[N];
void dijkstra(){
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[1] = 0;
q.push(make_pair(0,1));
while(!q.empty()){
int u = q.top().second;
q.pop();
if(vis[u])continue;
vis[u] = 1;
for(int i = h[u];i;i = a[i].next){
int v = a[i].v,w = a[i].w;
if(dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
q.push(make_pair(-dis[v],v));
}
}
}
}
|
参考：【原创】算法系列——四种最短路算法：Floyd，Dijkstra，Bellman-Ford，SPFA