是否有一种算法可以解决 linear time 中的单对最短路问题（即有向和无向边或无向边表示为两个有向边）， negative, real edge-weights 和 non-negative cycles ？
Wikipedia仅提及问题的单源和全对变体的算法 . 我知道解决其中一个问题的这些问题也解决了单对问题，但是它们都没有在线性时间和所有上述标准中起作用 .
因此，对于具有上述所有标准的单对最短路径问题，是否存在线性时间算法？
不，那里没有 . 直观地，没有允许负边缘权重的单对最短路径算法可以比单源算法更渐近有效，因为找到到达目标的最短路径可能在最坏的情况下涉及找到到达某个固定比例中的每一个的最短路径 . 其他节点（为了确定是否值得绕开每个负重边缘） .
1 回答
不，那里没有 . 直观地，没有允许负边缘权重的单对最短路径算法可以比单源算法更渐近有效，因为找到到达目标的最短路径可能在最坏的情况下涉及找到到达某个固定比例中的每一个的最短路径 . 其他节点（为了确定是否值得绕开每个负重边缘） .