破解60年前谜题！哥本哈根大学研究人员解决「单源最短路径」问题

---

  新智元报道  

论文链接：https://arxiv.org/abs/2203.03456

Wulff-Nilsen以Johnson的价格算法为基础。提出：在图像G = (V, E, w)中，令Φ为任意函数：V→Z。令w(Φ)为权函数：

定义：，则：。在图像G = (V, E,w)和图像G' = (V, E,w')中，若：1）图像G中的最短距离与图像G’中的最短距离相等，反之亦然；2）G只在G'含有负权环时含有负权环，则图像G与图像G'相等。

推论2.7考虑到任意图像和价格函数Φ。在 u, v ∈ V 中，

。而在任意环C中，

。因此，G和相等。如果，，那么G和G'相等。

该算法的目的是在计算价格函数Φ时，在GΦ中的所有边权都为非负，假设不存在负权环。之后就可以在上运行Dijkstra算法。

如果G是一个DAG（有向无环图），计算一个价格函数Φ，使具有非负权边是很简单的：只需在拓扑的v1, ..., vn上循环，并设置Φ(vi)，使所有进入的边权值为非负。

ScaleDown算法分阶段运行，在最后一个阶段它用ElimNeg（）来计算价格函数Φ2。如果ElimNeg终止，它将返回价格函数ψ′，让所有边值非负；换句话说，因为，所以中不包含负权值。

这意味着，对于所有，都满足条件（因为）。由此证明了 ScaleDown输出的正确性。

如果算法终止，则对于所有和，是积分，并且对于所有，。

这意味着对于所有，。因此图形G*具有非负权值。

通过归纳法，假设该理论适用于，算法第5行中对ScaleDown的调用满足必要的输入属性。

因此，通过和ScaleDown的Output，可以得到。

由于，若令C为中任意负权环，由于中的所有权值都为2n的倍数，且；又知，故与推论2.7不符。

从而得出结论：如果包含负权环，则算法不会终止。

去年，Wulff-Nilsen在同一领域取得了另一项突破，结果涉及如何在随时间变化的网络中找到最短路径。他对最近谜语的解决方案建立在这项工作的基础上。