让G(V,E)是有边长度的有向加权图,一些边的长度为负。给定顶点,找到计算最短路径的算法。
我的工作:
我正在考虑使用Johnson算法的重加权技术。然后,运行一次Belford Algo,然后应用Dijkstra v次。这将使我的时间复杂度为O(v ^ 2 log v + ve)。
对于这种问题,更改图形通常比更改算法容易得多。我们将两个负权重边称为N1和N2。根据定义,路径不能多次使用同一条边,因此有四种路径:
因此我们可以用原始图的每个节点的四个副本构造一个新图,这样对于原始图中的每个节点u
,(u, A)
,(u, B)
,(u, C)
和(u, D)
是节点在新图中。新图中的边如下:
u-v
,在新图形中该边线有四个副本(u, A)-(v, A)
... (u, D)-(v, D)
。新图中的每个边与原始图中的相应边具有相同的权重。现在,我们可以运行任何标准的单源最短路径问题,例如Dijkstra的算法,在新图中仅一次。从源到原始图形中节点u
的最短路径将是新图形中以下四个路径之一,无论哪个与原始图形中权重最低的路径相对应:
(source, A)
至(u, A)
。(source, A)
至(u, B)
,新图中的权重减去N1的权重。(source, A)
至(u, C)
,新图中的权重减去N2的权重。(source, A)
至(u, D)
,新图中的权重减去N1和N2的权重。由于新图具有4V顶点和4E-2条边,所以Dijkstra算法的最坏情况是O((4E - 2) + 4V log 4V)
,根据需要将其简化为O(E + V log V)
。
为了确保新图中的最短路径与原始图中的真实路径相对应,有待证明从(source, A)
至(u, B)
将不使用原始图形中相同边的两个副本。这很容易显示,但是我会考虑的事留给您。