线性时间单一
是否有一种算法可以解决混合图形 （即有向和无向边或无向边表示为两个有向边） 在线性时间内的单对最短路径问题，并具有负的，实际的边权重和非负周期 ？
维基百科只提到了单一来源和全对变种问题的算法。 我知道解决这些问题之一的这些问题也解决了单对问题，但是它们都不能在线性时间和以上所有标准下工作。
那么，对于上述所有标准的单对最短路径问题，是否存在线性时间算法？
不，那里没有。 直观地说，没有一个允许负边权重的单对最短路径算法比单一源算法更有渐近效率，因为找到到目标的最短路径可能在最坏的情况下涉及到找到每个固定比例的最短路径的其他节点（为了确定它是否值得绕开每个人的负重边）。
链接地址: http://www.djcxy.com/p/35255.html上一篇: Linear time single