Dijkstra 算法

Quote

迪杰斯特拉算法 （Dijkstra）是由荷兰计算机科学家狄克斯特拉于 $1959$ 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。¹

引入

首先，我们一下就可以想到一个暴搜：我们用 BFS 搜索每一个点，然后往外拓展，如果发现了更优那么就进入队列。但是，这种算法的时间复杂度非常高，而且我们可以发现每一个点进入队列的时候其实当时的距离不一定是最优的，但是后面获得了更优的值，因此这一个点就会重复进入队列，然后再更新一遍，因此时间复杂度非常高。

算法思想

我们能够采取一些优化。对于非负权图，我们可以发现每一次的转移都是优不断转移到更劣的，因此我们只需要每一次都找到最优的状态，然后将这个点转移到后面，也就是更劣的状态。这里我们就利用了路径长度这个递增的拓扑序来求解了最短路问题，时间复杂度为 $\mathcal{O}(n^2)$。

但是我们发现，其实没有必要每一次都花费 $\mathcal{O}(n)$ 的时间去找到距离最优的状态，而是采用一个二叉堆进行快速地访问，那么我们找到一个最优的状态的时间复杂度就变成了 $\mathcal{O}({\log }_{2}n)$，总时间复杂度就变成了 $\mathcal{O}((n+m){\log }_{2}n)=\mathcal{O}(m{\log }_{2}n)$。

注意 STL 当中的优先队列如果更新了最短路的长度是，那么我们无法删除和更改以前的状态，因此队列的元素数量就变成了 $m$ 个，时间复杂度就降到了 $\mathcal{O}(m{\log }_{2}m)$。其实我们的 set 是可以判断是否存在状态的，但是由于常数过大一般不会使用。

注意

Dijkstra 只能处理正边权的最短路和负边权的最长路，如果在负边权中求最短路很有可能会死循环或求出错误的答案。如果想要求出负边权图的最短路，请转去隔壁看 Bellman-Ford 算法。

警告

在稠密图当中，$m$ 可能近似于 $n^2$，这时使用堆优化 Dijkstra 的时间复杂度会达到 $\mathcal{O}(n^2{\log }_{2}n)$（或 $\mathcal{O}(n^2{\log }_2{n}^2)$），比朴素 Dijkstra 的 $\mathcal{O}(n^2)$ 要劣。

代码

朴素算法

void dijkstra(int s) {
  fill(f + 1, f + n + 1, 1e9);
  d[s] = 0;
  for (int i = 1; i <= n; i++) {
    int t = 0, mn = 1e9;
    for (int j = 1; j <= n; j++) {
      if (!f[j] && d[j] < mn) {
        t = j, mn = d[j];
      }
    }
    f[t] = 1;
    for (auto j : e[t]) {
      if (d[t] + j.v < d[j.to]) {
        q.push(j.to, d[j.to] = d[t] + j.v);
      }
    }
  }
}

使用优先队列优化

void dijkstra(int s) {
  fill(d + 1, d + n + 1, 1e9);
  for (q.emplace(s, 0), d[s] = 1; q.size(); q.pop()) {
    Node t = q.top();
    if (f[t.to]) {
      continue;
    }
    f[t.to] = 1;
    for (int i : e[t.to]) {
      if (d[t.to] + i.v < d[i.to]) {
        q.emplace(i.to, d[i.to] = d[t.to] + i.v);
      }
    }
  }
}

---

1. 来自百度百科，进行了一定处理。 ↩

评论