首页 文章

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

提问于
浏览 次
1

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

我猜我需要将我的给定图形以某种方式转换为具有非负权重的新图形，该图形中从s到v的最短路径将等于给定图形中所需的最短路径...或者我可能需要修改Dijkstra的算法？

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

algorithm graph dijkstra shortest-path

2 回答

  • 2

    由于Dijkstra 's algorithm is greedy, it won'吨使用负权重 . 为此需要一些其他算法，如the Bellman-Ford Algorithm .

    但是，如果您仍想使用Dijkstra算法，则有一种已知的方法 . 在这种方法中，您需要重新分配成本，以便所有成本都变为正数 .

    为此你可以看看 Johnson's Algorithm . 约翰逊的算法包括以下步骤（取自Wikipedia）：

    • 首先，将新节点q添加到图形中，通过零权重边缘连接到每个其他节点 .

    • 其次，使用Bellman-Ford算法，从新的顶点q开始，为每个顶点v找到从q到v的路径的最小权重h（v） . 如果此步骤检测到负循环，则算法为终止 .

    • 接下来，使用Bellman-Ford算法计算的值重新加权原始图的边缘：从u到v的边，长度为w（u，v），给出新的长度w（u，v）h（ u） - h（v） .

    • 最后，q被移除，Dijkstra算法用于找到从重新加权图中每个节点到每个其他顶点的最短路径 .

    回复于
  • 2

    Just some definitions to start:

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

    • 将要查找的最短路径的起始和结束顶点分别定义为 s 和 e .

    The basic idea:

    对负起重量边缘的起始顶点和每个末端顶点的每个组合运行Dijkstra算法多次，作为起始点和末端顶点以及负权重边缘的每个起始顶点作为结束点，并使用这些值找到实际的最短路径 .

    The algorithm:

    • 使用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

    既然有's a constant 7 runs of Dijkstra'的算法，
    运行时间为 O(7(|E| + |V| log |V|)) = O(|E| + |V| log |V|) .

    回复于

相关问题