Dijkstra 算法 | guanghechen

约定
¶

单元最短路径算法用于计算源点到图中所有点的最短距离。为方便表述，以下说明中进行如下约定：

记图 $G$ 的点集为 $V$ ，边集为 $E = {(x, y) | x \in V, y \in V}$
记边权为 $w_{x, y}$ （若存在多条从 $x$ 连向 $y$ 的边，取权值最小的那条）
记源点为 $s, (s \in V)$ ， $s$ 到 $x$ 的 真实最短距离 为 $D_{x}, (x \in V)$
记 $d_{x}$ 表示 $s$ 到 $x$ 的 当前已知最短距离，故 $D_{x} ⩽ d_{x}$ 恒成立；

为方便描述，以下称在边 $(x, y) \in E$ 中， $x$ 为 $y$ 的父跳转点。

算法描述
¶

初始化 $d_{x}$ ，使得 $d_{x} = {\begin{aligned} 0, & x = s \\ + \infty, & x \neq s \end{aligned}, x \in V$ ，准备一个空集合 $V^{'}$
在 $V - V^{'}$ 中选取点 $x$ 满足 $d_{x} = min {d_{z} | z \in V - V^{'}}$ ，将 $x$ 放入集合 $V^{'}$ 中
（松弛操作）用上一步获得的 $x$ 更新从 $x$ 出发的边 $(x, y)$ （实际上仅更新 ${(x, y) | y \in V - V^{'}}$ 中的边就可以了）：令 $d_{y} = min {d_{y}, d_{x} + w_{x, y}}$
重复第 2 步，直到 $V = V^{'}$

算法结束后，有 $V = {x | d_{x} = D_{x}, x \in V}$

算法原理
¶

不难发现， $V^{'} = {x | d_{x} = D_{x}, x \in V^{'}}$ 恒成立。这可以使用数学归纳法进行证明：

初始时，算法第 2 步取出的点必为 $s$ ，故此时结论成立。
不妨假设在算法运行中期时，结论仍成立，此时算法第 2 步取出的点为 $x$ ，由算法第 3 步中的松弛操作可知，当前 ${d_{z} | d_{z} \in V - V^{'}}$ 是在点 $z$ 尝试了以 ${y | y \in V^{'}}$ 中的任意（所有）点 $y$ 作为父跳转点（即最短路中使用了边 $y \to z$ ）后计算出的值
若此时 $d_{x} > D_{x}$ ，则 $x$ 必然只能选取 $V - V^{'}$ 中的点作为父跳转点才能得到最短路径，又因为 $d_{x} = min {d_{z} | z \in V - V^{'}}$ ，即如果这种情况真的成立，则必有 $\exists z_{0} \in V - V^{'}$ 使得 $D_{z_{0}} + w_{z_{0}, x} ⩽ d_{x}$ ，因为 dijkstra 处理的是正边权的图，故有 $D_{z_{0}} < d_{x}$ ，且 $z_{0}$ 的父跳转点必不在 $V^{'}$ 中，否则此时 $d_{z_{0}} = D_{z_{0}}$ （因为父跳转点在 $N^{'}$ 中意味着已求出从 $s$ 到 $z_{0}$ 父跳转点最短距离，则此时也就求出了 $D_{z_{0}}$ ），这与 $d_{x} ⩽ d_{z_{0}} ⩽ D_{z_{0}}$ 矛盾。
类似地可证明此时 $z_{0}$ 的父跳转点的父跳转点也不在 $V^{'}$ 中，递归下去即整条从 $s$ 到达 $z_{0}$ 的路径上都不存在 $V^{'}$ 中的点，但这是不可能的，因为 $s$ 就在 $V^{'}$ 中，故这样的 $z_{0}$ 并不存在。
因此此时 $d_{x} = D_{x}$ ，即 $x \in V^{'}$ .

HINT

由上述关于 $D_{z_{0}} + w_{z_{0}, x} ⩽ d_{x}$ 的假设可知，若存在非正边权，则无法推导出 $D_{z_{0}} < d_{x}$ 的结论，此时算法将失效。具体地，参见下图的说明：

优化
¶

不难发现，上述算法中总共迭代 $‖ V ‖$ 次，每次又遍历 $O (‖ V ‖)$ 次去寻找 $x$ ，故时间复杂度为 $O (‖ V ‖^{2})$ .

如果采取邻接表来存储边，则最多累计进行 $‖ E ‖$ 次松弛操作，此时算法瓶颈在于寻找满足 $x, (d_{x} = min {d_{z} | z \in V - V^{'}})$ ，可以使用优先队列（或小根堆）来维护 $d$ 值，则可以在 $O (\log ‖ V ‖)$ 的复杂度内找到 $x$ 。但是因为优先队列不支持修改值，所以，对于松弛成功点 $y$ ，需要将此时的 $d_{y}$ 重新扔入优先队列中。这样一来需要增加一个额外的判断：即优先队列中弹出的元素 $y$ 是否已属于 $V^{'}$ 。若是，则跳过处理。时间复杂度为 $O (‖ E ‖ \log ‖ V ‖)$ .

程序实现
¶

为方便表述，约定如下变量含义：

N 表示图中点的个数，即 N $= ‖ V ‖$ ，并假定图中所有点按 $[0,$ N $- 1]$ 进行标号
INF 表示一个超过最长路径长度的超大值
s 表示源点
w[x][y] 表示边 $(x, y)$ 的边权，即 w[x][y] $= w_{x, y}$
d[x] 对应上文中提到的 $d$ 数列，即 d[x] $= d_{x}$
visited[x] 表示点 $x$ 是否在集合 $V^{'}$ 中，即 visited[x] $= {\begin{aligned} t r u e, & x \in V^{'} \\ f a l s e, & x \in V - V^{'} \end{aligned}$

朴素 dijkstra 算法 (C++)

dijkstra.pure.cpp | 27 lines.

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
const int INF = 0x3f3f3f3f;

void dijkstra(int N, int s, int** w, int* d, bool* visited) {
  // Initialize the `d` array.
  for (int x = 0; x < N; ++x) {
    d[x] = INF;
    visited[x] = false;
  }
  d[s] = 0;

  for (int u = 0; u < N; ++u) {
    int x, m = INF;
    for (int z = 0; z < N; ++z) {
      if (visited[z]) continue;
      if (d[z] <= m) m = d[x = z];
    }

    if (m == INF) break;

    // Perform the relaxation operation.
    visited[x] = true;
    for (int y = 0; y < N; ++y) {
      int v = d[x] + w[x][y];
      if (d[y] > v) d[y] = v;
    }
  }
}

优先队列优化的 Dijkstra 算法 (Typescript)

dijkstra.priority-queue.ts | 43 lines.

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
34
35
36
37
38
39
40
41
42
43
import { PriorityQueue } from '@algorithm.ts/queue'

export interface DijkstraEdge<T extends number | bigint> {
  /**
   * The other end of the edge.
   */
  to: number
  /**
   * The cost of walking along this side.
   */
  cost: T
}

export function dijkstra<T extends number | bigint>(
  N: number,
  source: number,
  G: Array<Array<DijkstraEdge<T>>>,
  ZERO: T,
  INF: T,
): T[] {
  const dist: T[] = new Array(N).fill(INF)
  const Q = new PriorityQueue<{ pos: number; cost: T }>({
    compare: (x, y) => x.cost - y.cost,
  })

  // eslint-disable-next-line no-param-reassign
  dist[source] = ZERO
  Q.enqueue({ pos: source, cost: ZERO })

  while (Q.size > 0) {
    const { pos, cost } = Q.dequeue()!
    if (dist[pos] < cost) continue
    for (const e of G[pos]) {
      const candidate: T = (dist[pos] as any) + e.cost
      if (dist[e.to] > candidate) {
        // eslint-disable-next-line no-param-reassign
        dist[e.to] = candidate
        Q.enqueue({ pos: e.to, cost: dist[e.to] })
      }
    }
  }
  return dist
}

约定¶

算法描述¶

算法原理¶

优化¶

程序实现¶

Related¶

约定
¶

算法描述
¶

算法原理
¶

优化
¶

程序实现
¶

Related
¶