从源到图中所有节点的最短路径距离-O（m + n log（n））时间

Question

让G（V，E）是具有边长的有向加权图，其中所有边长为正，除了其中两条边的长度为负。给定固定的顶点s，请给出一种算法，以在O（e + v log（v））的时间内计算从s到任何其他顶点的最短路径。

我的工作：

我正在考虑使用Johnson算法的重加权技术。然后，运行一次Belford Algo，然后应用Dijkstra v次。这将使我的时间复杂度为O（v ^ 2 log v + ve）。这是标准的全对最短问题，因为我只需要一个顶点-我的时间复杂度将是O（v log v + e）对吗？

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的权重。