》，在一个带权有向图G=(V,E)中，每条边的权值都是实数。另外，给定一个顶点，称为源。计算从源到每个其他顶点的最短路径的长度是单源最短路径(SSSP)问题。”半个多世纪以来，世界各地的研究人员一直在努力解决这个问题，如今，这个算法难题终于被哥本哈根大学计算机科学系的一个研究团队解决了。高效论文链接：https://arxiv.org/abs/2203.03456研究员ChristianWulff-Nilsen在接受采访时表示，他们的解决方案是30多年来首次突破?(n(4/3)logW)时间约束负权重的SSSP组合算法，SSSP有两种经典算法：迪杰斯特拉算法（Dijkstraalgorithm）和贝尔曼-福特算法（Bellman-Fordalgorithm），两者都有各自的局限性。达到近线性时间O(m+nlogn)，但无法计算负权边，Bellman-Ford算法可以计算负权边，但计算时间过长，达到O(mn)。解决负权边的topSSSP算法都依赖于复杂的连续优化和动态代数和图算法。结果，即使后世学者不断优化算法，其运算时间仍需?(n(4/3)logW)。这种计算时间限制已经存在了三十年。面对这些局限性，Wulff-Nilsen提出了两个问题：1）负权边算法的运行能否达到近线性时间？2）这可以用简单的工具来实现吗？有没有既需要时间又需要质量的方法？别说了，真的有。Wulff-Nilsen提出的算法是一种图像缩放算法，由简单的图像分解算法LowDiameterDecomposition增强。通常，这种分解算法只用于非负权边的图分解，本研究的贡献之一是将其应用于负权边图像，强化负权边SSSP递归缩放算法。Wulff-Nilsen的推导过程基于约翰逊的价格算法。提议：在图像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'相等。该算法的目的是在计算价格函数Φ时，GΦ中的所有边权重都是非负的，假设不存在负权重环。然后你可以在上面运行Dijkstra算法。之后，Wulff-Nilsen开始介绍自己的算法框架。首先，Wulff-Nilsen假设存在一个算法Dijkstra(G,s)，输入一个没有负权边的图G，顶点s∈V，G中的s输出最短路径树。运行时间为O(m+nlogn)。如果G是DAG（有向无环图），则计算价格函数Φ使得具有非负权重的边是微不足道的：只需循环拓扑的v1,...,vn并设置Φ(vi)，以便所有传入的边权重都是非负的。单源最短路径问题的目标是找到从给定起始节点到网络中所有其他节点的最短路径。网络表示为由节点和它们之间的连接组成的图，称为边。每条边都有一个方向（例如，这可以用来表示单行道）和一个表示沿该边行驶的成本的权重。如果所有边的权重都是非负的，则可以使用经典的Dijkstra算法在几乎线性时间内解决该问题。新的结果几乎与Dijkstra的算法同时解决了这个问题，而且还允许负边权重。随后，Wulff-Nilsen提到了组合工具中最重要的两个算法：ScaleDown和SPmain。ScaleDown算法分阶段运行，在最后阶段它使用ElimNeg()计算价格函数Φ2。如果ElimNeg终止，则返回价格函数ψ′使得所有边值都是非负的；换句话说，因为，所以不包含负权重。这意味着，对所有人来说，条件（因为）都得到满足。这证明了ScaleDown输出的正确性。如果算法终止，则对于所有和，是积分，并且对于所有。这意味着对所有人来说，.因此图G*具有非负权重。通过归纳，假设该理论适用，算法第5行中对ScaleDown的调用满足必要的输入属性。因此，通过ScaleDown的Output，可以得到。因为，如果令C为中的任何负权重环，由于中的所有权值都是2n的倍数，并且；亦知，与推论2.7不符。因此可以得出结论，如果包含负权重环，算法将不会终止。可以证明SPmain算法的正确性。至此，Wulff-Nilsen的负权重SSSP解决方案中最重要的两个算法已经得到证明。新算法在保证近线性时间的同时成功地引入了负权重。60年后，寻找答案不仅仅是解谜去年，Wulff-Nilsen在同一领域取得了另一项突破，涉及如何在随时间变化的网络中找到最短路径。他对最近一个谜语的解答是建立在这项工作的基础上的。他认为，解决SSSP问题可以为算法铺平道路，这些算法不仅可以帮助电动汽车立即计算出到达目的地的最快路线，而且可以保证以最节能的方式进行计算。Wulff-Nilsen解释说：“我们的算法加入了负权重，这是以前算法没有的维度。一个实际的例子是，在山区行驶时，有了负权重的维度，导航系统可以为电动车推荐下坡路。车主多开路线，让电动车下坡时也能充电。Wulff-Nilsen还表示，他们的算法不仅可以用于电动汽车的路线规划，还可以用于金融行业的投机监控。投机者以各种货币进行投机的银行。现在很多不法分子利用电脑作案，但是因为我们的算法速度太快了，也许可以用来监控，在人钻空子之前及时发现。”1959年，当Dijkstra首次提出最短距离问题，他可能没有想到，60多年来，人们一直在不断优化这个问题的解法。你可能也会惊讶于谜语的答案竟有如此丰富的内涵，或许这就是科学的魅力吧.
