HKE 算法¶

前言¶

HKE 算法是由好渴鹅发现的，但是网上并没有找到关于这个算法的任何信息，因此这个非常优秀的算法大家可能根本就不会学习到。由于这个算法网上并没有任何命名，因此暂时称作 HKE 算法。如果发现了某一篇论文里面提出了该算法，请在本文章的评论去内评论原作者，并联系好渴鹅进行删改。

引入¶

众所周知，图的最短路算法有“三大天王”，分别为 Bellman-Ford 算法、Dijkstra 算法和 Floyd 算法。其中，Dijkstra 算法的复杂度最好，朴素复杂度有 \(\mathcal O(n^2)\)，加入了堆优化可以达到 \(\mathcal O(m\log_2 n)\)（或 \(\mathcal O(m\log_2 m)\)）的时间复杂度。而 Bellman-Ford 算法和主要用于求解带有负权的图的最短路，加入队列优化（SPFA）最好可以达到 \(\mathcal O(n+m)\) 的时间复杂度，但是最坏情况下可以被构造数据卡到 \(\mathcal O(nm)\)。

Floyd 主要求解任意两点之间的最短路，预处理的时间复杂度为 \(\mathcal O(n^3)\)。不过，在没有负权的情况下，跑 \(n\) 遍 Dijkstra \(\mathcal O(nm\log_2 m)\) 的复杂度可能在稀疏图中跑的更快。

那么，对于一些特殊情况（例如有向图等），有没有比“三大天王”的复杂度还要更有的算法呢？

算法简介¶

好渴鹅则想出了 HKE 算法。对于有向无环图（DAG），HKE 算法可以在 \(\mathcal O(n+m)\) 的时间复杂度之内求出单个点到其他点的最短路，并且支持负边权。

HKE 算法的核心思想是动态规划。对于有向无环图，一个点的最短路只能由这个点的入边的邻点而来。那么对于 \(1\sim i\) 的路径，不管中间经过了那些点，只要使得路径最短即可。因此我们在处理最短的时候我们并不在意一条路径本身，而是只存储一条路径它的终点。如果两条路径终点一样，那么我们只需要保留长度最短的其中一个即可。

那么从源点到哪一个点就是状态分组，而中间的长度则是分组的最优化属性。同一个状态分组的最优化属性只有一个。设 \(dp_i\) 表示为 \(1\sim i\) 的最短距离，那么源点到源点的距离肯定是 \(0\)，那么 \(dp_s=0\) 就是我们的初始状态。

接下来考虑转移，点 \(i\) 的最短路只能由点 \(j\)（\(j\) 往 \(i\) 有一条边）而来，那么 \(dp_i\) 则等于所有 \(dp_j\) 加上 \(w(j,i)\) 的距离当中的最短路，即 \(dp_i=\min(dp_i,dp_j+w(j,i)[j\to i])\)。

转换一下，我们正向转移，则不是从前面的入边转移过来，而是转移到后面的出边。显然，\(dp_i\) 的值可以决定 \(dp_j\)，当且仅当 \(i\) 往 \(j\) 有一条边。同样，\(dp_j\) 需要取最小距离，即 \(dp_j=\min(dp_j,dp_i+w(i,j))[i\to j]\)。

为什么要往后面转移

如果是收集前面的入边的子问题的答案来转移的话，那么获取入边就需要存反图，因为不存反图只能访问所有的出边，空间复杂度就需要两倍的常数，但时间复杂度未必更优秀。

但是我们发现，\(dp_i\) 可能没有被求解，就已经被转移了。反向思路，就是 \(dp_j\) 转移过来的 \(dp_i\) 的子问题不一定已经求解过。主要原因是因为图没有拓扑序，所以使用动态规划求解会有问题。

因此，我们就可以使用拓扑排序来求出求解的顺序。这样子，我们的 \(i\) 如果按照拓扑排序之后的拓扑序来循环的话，那么 \(dp_j\) 就一定是求解过的了。

代码

void solve(int s) {
  fill(dis + 1, dis + n + 1, 1e9);
  // 拓扑排序
  for (q.push(1), v.push_back(1), dis[s] = 0; q.size(); q.pop()) {
    for (auto i : e[q.front()]) {
      if (!--ind[i.first]) {
        v.push_back(i.first);
        q.push(i.first);
      }
    }
  }
  // 根据拓扑序求解
  for (int i : v) {
    for (auto j : e[i]) {
      dis[j.first] = min(dis[j.first], dis[i] + j.second);
    }
  }
}

最后我们可以发现在拓扑排序的时候就可以顺便动态规划了，因此就可以得到更短的代码。

更短的代码

void solve(int s) {
  fill(dis + 1, dis + n + 1, 1e9);
  for (q.push(1), dis[s] = 0; q.size(); q.pop()) {
    for (auto i : e[q.front()]) {
      dis[i.first] = min(dis[i.first], dis[q.front()] + i.second);
      if (!--ind[i.first]) {
        q.push(i.first);
      }
    }
  }
}

时间复杂度¶

拓扑排序：每一个点只会进入队列一次，需要因此每一个点的所有出边只会被遍历一次（忽略点 \(s\) 的入边），因此时间复杂度为 \(O(n+m)\)。

动态规划：与拓扑排序一样，转移 \(\mathcal O(1)\)。

因此，HKE 算法的时间复杂度为 \(\mathcal O(n+m)\)。

为什么只支持 DAG¶

首先，如果图当中有环，那么无法进行拓扑排序，无法进行动态规划。其次，如果图是双向图，那么也无法进行拓扑排序，导致无法进行动态规划。

但是 HKE 算法支持负边权，因为 HKE 算法的拓扑序并不像 Dijkstra 依赖不断递增的路径长度，而是依赖于结点拓扑序。因此，负边权不会影响拓扑序，也就不会影响动态规划的求解。

后记¶

本文章由好渴鹅原创，采用 CC-BY-NC 协议发布。转载请注明出处，请勿用于商业用途。若发现雷同，均为巧合。