“更快的最短路 2”？

“更快的最短路 2”，相信不少人听到这样一件事都会很震惊，小编也感到如此呢。
那么今天就随小编来一起看看吧。

上期视频我们讨论了 SPFA，但它已经众所周知了。显然配不上“更快的最短路”这一名号。
于是，小编打算找寻更快的最短路算法。

但正如之前所说，众所周知的算法配不上这一名号。所以小编打算自己发明一个算法。
首先我们讨论非负权：

这显然可以贪心，但这会导向 Dijkstra，而它的复杂度是肯定不低于排序的，现在已经优化到头了（$O(m+n \log n)$），这不行。
那我们不贪心，考虑非负权有什么好性质，发现其肯定满足最小 dist 原理，这就导向 Dijkstra。
但小编明明想要发明一种算法，这不行。
非负权肯定指向 Dijkstra，这无法避免，因此我决定魔改 Dijkstra。
我们考虑上一个堆解决这个问题，但这显然是已有的的。
小编在想象学竞赛中，曾经想象到了一篇文章叫做“《论现代硬件上的常数优化》”，其中提到写非递归线段树会跑得更快，但实机测试并非如此，可能是小编的实现太烂了，况且这也只是常数优化，不能配上“更快的最短路”这一名号。

于是小编放弃了 Dijkstra，转而探寻别的。
考虑 dX 指引了一条道路叫做稀疏图，这自然而然地让人想想到“稀疏图上更快的最短路”，但那个东西小编不喜欢，它也是基于随机化的，复杂度也很丑，这不好。
考虑 dX 没有指引的一条道路叫做平面图，但已经有算法做到理论最优了，这也不行。

于是小编找寻另外一条魔改路径，毕竟排序就是快排缝上 $10^9$ 种优化和别的算法得到的，考虑 Dijkstra 还能缝上什么。
缝上亚 $\log$ 数据结构？缝上分块？缝上 Fusion Tree？
但小编写都没写过。

以及探索最后一条路径，考虑缝上 Bellman-Ford。
但这条路好像也被探索过了，似乎在去年 7 月出现了一个，成功打破 Dijkstra 的 $O(m \log^{2/3} n)$ 的算法。
真是令人震惊啊。

非负权无向图也有一个理论线性的做法。
其实接着探寻更快的最短路感觉已经在 OI 方面没什么用了，更好的复杂度似乎停留在理论计算机科学层面。
但不可否认它们对人类计算机事业的贡献。

但今天是星期四，小编要去整点薯条了，顺带祝大家新年快乐喵。
好啦今天的视频到这里就结束了，关注小编不迷路，我们下期视频再见。

注：不保证以上内容可靠性，如果有错，就说明是 AI 生成的。