HKE 算法¶
前言¶
HKE 算法是由好渴鹅发现的,但是网上并没有找到关于这个算法的任何信息,因此这个非常优秀的算法大家可能根本就不会学习到。由于这个算法网上并没有任何命名,因此暂时称作 HKE 算法。如果发现了某一篇论文里面提出了该算法,请在本文章的评论去内评论原作者,并联系好渴鹅进行删改。
引入¶
众所周知,图的最短路算法有“三大天王”,分别为 Bellman-Ford 算法、Dijkstra 算法和 Floyd 算法。其中,Dijkstra 算法的复杂度最好,朴素复杂度有
Floyd 主要求解任意两点之间的最短路,预处理的时间复杂度为
那么,对于一些特殊情况(例如有向图等),有没有比“三大天王”的复杂度还要更有的算法呢?
算法简介¶
好渴鹅则想出了 HKE 算法。对于有向无环图(DAG),HKE 算法可以在
HKE 算法的核心思想是动态规划。对于有向无环图,一个点的最短路只能由这个点的入边的邻点而来。那么对于
那么从源点到哪一个点就是状态分组,而中间的长度则是分组的最优化属性。同一个状态分组的最优化属性只有一个。设
接下来考虑转移,点
转换一下,我们正向转移,则不是从前面的入边转移过来,而是转移到后面的出边。显然,
为什么要往后面转移
如果是收集前面的入边的子问题的答案来转移的话,那么获取入边就需要存反图,因为不存反图只能访问所有的出边,空间复杂度就需要两倍的常数,但时间复杂度未必更优秀。
但是我们发现,
因此,我们就可以使用拓扑排序来求出求解的顺序。这样子,我们的
代码
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);
}
}
}
}
时间复杂度¶
拓扑排序:每一个点只会进入队列一次,需要因此每一个点的所有出边只会被遍历一次(忽略点
动态规划:与拓扑排序一样,转移
因此,HKE 算法的时间复杂度为
为什么只支持 DAG¶
首先,如果图当中有环,那么无法进行拓扑排序,无法进行动态规划。其次,如果图是双向图,那么也无法进行拓扑排序,导致无法进行动态规划。
但是 HKE 算法支持负边权,因为 HKE 算法的拓扑序并不像 Dijkstra 依赖不断递增的路径长度,而是依赖于结点拓扑序。因此,负边权不会影响拓扑序,也就不会影响动态规划的求解。
后记¶
本文章由好渴鹅原创,采用 CC-BY-NC 协议发布。转载请注明出处,请勿用于商业用途。若发现雷同,均为巧合。