Johnson算法

Question

如果给出负边缘权重，如何找到最短路径的约翰逊算法

Answer 1

对于这种问题，更改图形通常比更改算法容易得多。我们将两个负权重边称为N1和N2。根据定义，路径不能多次使用同一条边，因此有四种路径：

• A。既不使用N1也不使用N2的那些，
• B。使用N1但不使用N2的那些，
• C。使用N2但不使用N1的那些，
• D。同时使用N1和N2的用户。

因此我们可以用原始图的每个节点的四个副本构造一个新图，这样对于原始图中的每个节点u，(u, A)，(u, B)，(u, C)和(u, D)是节点在新图中。新图中的边如下：

• 对于原始图形中的每个正权重边线u-v，在新图形中该边线有四个副本(u, A)-(v, A) ... (u, D)-(v, D)。新图中的每个边与原始图中的相应边具有相同的权重。
• 对于第一个负权重边（N1），在新图中有该边的两个副本；一个从A层到B层，一个从C层到D层。这些新边的权重为0。
• 对于第二个负权重边（N2），在新图中有该边的两个副本；一个从A层到C层，一个从B层到D层。这些新边的权重为0。

现在，我们可以运行任何标准的单源最短路径问题，例如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)将不使用原始图形中相同边的两个副本。这很容易显示，但是我会考虑的事留给您。