在包含至多两个负边的图中寻找最短路径距离

 

我给出了一个有向图，其中每条边都有成本。利用图中最多有两个负边的事实，我的目标是找到从给定节点到V中所有节点的最短路径距离。算法的时间复杂度应该是O(|E| + |V|*log|V|) ，所以我认为我需要应用Dijkstra算法。

我猜测我需要将我给定的图表以某种方式翻译成具有非负权重的新图形，这个图形中从s到v的最短路径将等同于给定图形中所需的最短路径。或者我可能需要修改Dijkstra的算法？

我现在正在挣扎。 任何帮助，将不胜感激！

由于Dijkstra的算法很贪婪，因此它不适用于负权重。 你需要一些其他的算法，比如Bellman-Ford算法来达到这个目的。

但是，如果你仍然想使用Dijkstra算法，那么有一个已知的方法。 在这种方法中，您需要重新分配成本，以便全部变得积极。

为此您可以查看Johnson的算法 。 约翰逊的算法由以下步骤组成（摘自维基百科）：

  • 首先，将新节点q添加到图中，并通过零权重边连接到每个其他节点。
  • 其次，使用Bellman-Ford算法，从新顶点q开始，为每个顶点v寻找从q到v的路径的最小权重h（v）。如果该步骤检测到负循环，则算法终止。
  • 接下来，使用由Bellman-Ford算法计算的值重新加权原始图的边缘：具有长度w（u，v）的从u到v的边被赋予新的长度w（u，v）+ h（ u） - h（v）。
  • 最后，q被去除，并且Dijkstra的算法被用于找到从每个节点到重新加权图中的每个其他顶点的最短路径。

    • 只是一些定义开始：

  • 设负边为n1 = (n1s, n1e) （即从顶点n1s到顶点n1e ）
    和n2 = (n2s, n2e) 。

  • 将我们想要查找的最短路径的起点和终点分别定义为s和e 。

    • 基本理念：

    针对起始顶点和负重边的每个结束顶点的每个组合，多次运行Dijkstra算法作为起点和结束顶点以及负重边的每个起始顶点作为终点，并将这些值用于找到实际的最短路径。

    算法：

  • 使用Dijkstra算法确定以下最短路径，全部都不包括负边沿： 

    se   = s -> e                  // shortest path from s to e
sn1  = s -> n1s                // shortest path from s to n1
sn2  = s -> n2s                // shortest path from s to n2
ne1  = n1e -> e                // shortest path from n1 to e
n1n2 = n1e -> n2s              // shortest path from n1 to n2
ne2  = n2e -> e                // shortest path from n2 to e
n2n1 = n2e -> n1s              // shortest path from n2 to n1

  • 现在简单地计算最小值： 

    se                             // s to e
sn1 + n1 + ne1                 // s to n1 to e
sn2 + n2 + ne2                 // s to n2 to e
sn1 + n1 + n1n2 + n2 + ne2     // s to n1 to n2 to e
sn2 + n2 + n2n1 + n1 + ne1     // s to n2 to n1 to e

    • 由于Dijkstra算法有7次运行，
    运行时间将为O(7(|E| + |V| log |V|)) = O(|E| + |V| log |V|) 。

    链接地址: http://www.djcxy.com/p/35215.html

    上一篇: Finding shortest path distances in a graph containing at most two negative edges

    下一篇: Algorithm to modify the weights of the edges of a graph, given a shortest path