简介

Dijkstra算法是求解单源最短路的算法之一，核心思想是贪心，只适用于边权为正的无向和有向图。原复杂度$O(n^{2})$，优化后时间复杂度能到$O(mlog_{m})$。

Dijkstra算法

首先我们来看这个贪心性质：

从起点u到终点v的最短路径，一定是从起点u到这条最短路径上经过的点w的最短路径。

可以用反证法证明，假设$dis(u, w)$是起点u到终点v最短路径上的起点u到途经点w的距离。若存在不是最短路径上的$dis’(u, w) < dis(u, w)$，那么可以得出$dis’(u, w)+dis(w, v) < dis(u, w)+dis(w, v)$，即存在从起点u到终点v的更短的路径，与假设矛盾。

可以根据这个性质得到贪心思路，但是这个性质基于一个前提：

对于起点u的最短邻接边uw，从u到w不可能存在比$dis(u, w)$更短的路径。因为uw已经是最短的了，从其它路径走的话必然经过比uw更长的路径。

而这也是Dijkstra不能处理负边权的原因，如果有负边权则无法满足前提。可以看下图自行理解：

条件

那么，依据这个贪心性质得到思路，我们可以从现知的最短路径开始，去更新起点到其它点的距离，再更新已知的最短路，重复这个过程，遍历完所有的点之后，就能得到起点到其它点的最短路径长度。详细过程如下：

  1. 将起点加入已经确定最短路的集合S，其它点则属于未确定的集合V-S=T。
  2. 更新到起点的最短距离dis[i]。
  3. 选取未访问的最小的$dis[x ]$，标记并加入已经确定最短路的集合S，此时的dis[x ]就是x到起点的最短距离。
  4. 再依据$ dis[y]=min(dis[y], dis[x ]+{边权值}w[x ][y]) $，更新集合T中与x相邻的点y到起点的最短距离dis[y]。这个操作叫做松弛操作（relax），更新过后当前的不等式约束$ dis[y] $相对于$ dis+w[x ][y] $已经不是最“紧”的约束了，下一次更新dis[y]时就不需要检查这个约束了，即原约束被“松弛”了。
  5. 重复3，4步骤直到目标点加入集合，此时目标点对应的dis[v]就是最短路径长度。

邻接矩阵存图，核心代码如下：

 1void dijkstra(int s, int n)
 2{
 3    dis[s] = 0;
 4    for(int i=1; i<=n; i++)
 5    {
 6        int x = 0;
 7        for(int j=1; j<=n; j++)
 8            if(!vis[j] && (x==0 || dis[j]<dis[x])) x = j;
 9
10        vis[x] = 1;
11        for(int j=1; j<=n; j++)
12            dis[j] = min(dis[j], dis[x]+g[x][j]);
13    }
14}

优化

时间复杂度分析，只分析集合操作，n次delete-min，m次decrease-key。

  • 如果用暴力：$O(n^{2}+m)$。
  • 如果用堆：$O(mlog_{n})$。
  • 如果用priority_queue：$O(mlog_{m})$。
  • 如果用线段树（ZKW线段树）：$O(mlog_{n}+n)=O(mlog_{n})$。
  • 如果用Fibonacci堆：$O(nlog_{n}+m)$。

如果使用priority_queue，无法删除某一个旧的结点，只能插入一个权值更小的相同编号结点，这样操作导致堆中元素是$O(m)$的。

下面给出使用邻接表及priority_queue的优化版本，即优化了存图方式以及寻找未访问的最小dis结点过程。代码如下：

 1void dijkstra(int s, int n)
 2{
 3    q.push({dis[s]=0, s});
 4    while(!q.empty()){
 5        int u = q.top().second; q.pop();
 6        if(vis[u]) continue;
 7        vis[u] = 1;
 8        for(int i=H[u]; ~i; i=e[i].next){
 9            int v=e[i].to, w=e[i].w;
10            if(!vis[v] && dis[u]+w < dis[v]){
11                dis[v] = dis[u]+w;
12                pre[v] = u;
13                q.push({dis[v], v});
14            }
15        }
16    }
17}

模板

原始版本：

 1const int inf = 0x3f3f3f3f;
 2const int mxn = 1e3 + 5;
 3
 4int g[mxn][mxn];
 5
 6void graph_init(int n)
 7{
 8    for(int i=1; i<=n; i++){
 9        for(int j=1; j<=n; j++)
10            g[i][j] = inf;
11        g[i][i] = 0;
12    }
13}
14
15int dis[mxn], pre[mxn];
16bool vis[mxn];
17
18void dijkstra_init(int n)
19{
20    for(int i=1; i<=n; i++){
21        vis[i] = pre[i] = 0;
22        dis[i] = inf;
23    }
24}
25
26void dijkstra(int s, int n)
27{
28    dis[s] = 0;
29    for(int i=1; i<=n; i++)
30    {
31        int x = 0;
32        for(int j=1; j<=n; j++)
33            if(!vis[j] && (x==0 || dis[j]<dis[x])) x = j;
34
35        vis[x] = 1;
36        for(int j=1; j<=n; j++){
37            if(!vis[j] && dis[x]+g[x][j] < dis[j]){
38                dis[j] = dis[x]+g[x][j];
39                pre[j] = x;
40            }
41        }
42    }
43}
44
45int main()
46{
47    int n, m;
48    scanf("%d %d", &n, &m);
49    graph_init(n);
50
51    for(int i=0; i<m; i++)
52    {
53        int u, v, w;
54        scanf("%d %d %d", &u, &v, &w);
55        g[u][v] = w;
56    }
57    dijkstra_init(n);
58    dijkstra(1, n);
59
60    for(int i=1; i<=n; i++)
61        printf("%d ", dis[i]);
62    printf("\n");
63
64    for(int i=n; i; i=pre[i])
65        printf("%d ", i);
66    printf("\n");
67
68    return 0;
69}
70
71/*
72Sample Input:
73
744 5
751 2 2
761 3 4
772 4 1
783 2 1
793 4 8
80
81Sample Output:
82
830 2 4 3
844 2 1
85
86*/

优化版本：

 1const int inf = 0x3f3f3f3f;
 2const int mxn = 1e3 + 5;
 3
 4struct E {
 5    int to, next, w;
 6} e[mxn];
 7
 8int H[mxn], tot;
 9
10void add(int from, int to, int w) {
11    e[tot] = {to, H[from], w};
12    H[from] = tot++;
13}
14
15void graph_init(int n)
16{
17    for(int i=1; i<=n; i++)
18        H[i] = -1;
19    tot = 0;
20}
21
22int dis[mxn], pre[mxn];
23bool vis[mxn];
24priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
25
26void dijkstra_init(int n)
27{
28    for(int i=1; i<=n; i++){
29        vis[i] = pre[i] = 0;
30        dis[i] = inf;
31    }
32}
33
34void dijkstra(int s, int n)
35{
36    q.push({dis[s]=0, s});
37    while(!q.empty()){
38        int u = q.top().second; q.pop();
39        if(vis[u]) continue;
40        vis[u] = 1;
41        for(int i=H[u]; ~i; i=e[i].next){
42            int v=e[i].to, w=e[i].w;
43            if(!vis[v] && dis[u]+w < dis[v]){
44                dis[v] = dis[u]+w;
45                pre[v] = u;
46                q.push({dis[v], v});
47            }
48        }
49    }
50}
51
52int main()
53{
54    int n, m;
55    scanf("%d %d", &n, &m);
56    graph_init(n);
57
58    for(int i=0; i<m; i++)
59    {
60        int u, v, w;
61        scanf("%d %d %d", &u, &v, &w);
62        add(u, v, w);
63    }
64    dijkstra_init(n);
65    dijkstra(1, n);
66
67    for(int i=1; i<=n; i++)
68        printf("%d ", dis[i]);
69    printf("\n");
70
71    for(int i=n; i; i=pre[i])
72        printf("%d ", i);
73    printf("\n");
74
75    return 0;
76}
77
78/*
79Sample Input:
80
814 5
821 2 2
831 3 4
842 4 1
853 2 1
863 4 8
87
88Sample Output:
89
900 2 4 3
914 2 1
92
93*/