1

当我在Algorithms, 4th edition, Robert Sedgewick and Kevin Wayne一书中遇到以下问题时，我最近正在了解最短路径算法。

假设我们通过在 EdgeWeightedDigraph 中为 EdgeWeightedGraph 中的每个 Edge 创建两个 DirectedEdge 对象（每个方向一个）将 EdgeWeightedGraph 转换为 Directed EdgeWeightedGraph，然后使用 Bellman-Ford 算法。解释为什么这种方法会失败。

下面是我实现贝尔曼福特算法（基于队列）的一段代码：

private void findShortestPath(int src) {
    queue.add(src);
    distTo[src] = 0;
    edgeTo[src] = -1;
    while (!queue.isEmpty()) {
        int v = queue.poll();
        onQueue[v] = false;
        for (Edge e : adj(v)){
            int w = e.dest;
            if (distTo[w] > distTo[v] + e.weight) {
                distTo[w] = distTo[v] + e.weight;
                edgeTo[w] = v;
            }
            if (!onQueue[w]) {
                onQueue[w] = true;
                queue.add(w);
            }

            //Find if a negative cycle exists after every V passes
            if (cost++ % V == 0) {
                if (findNegativeCycle())
                    return;
            }
        }
    }
}

我在纸上尝试了许多示例，但无法找到生成的有向图将在其中包含新的负循环的场景，只需将一条边转换为相反方向的两条边即可。我假设在未加权的无向边加权图中没有预先存在的负循环。

4

1 回答 1

-2

您的算法和代码没有问题。它可以在没有负圆的情况下给出图中的最短距离。并且只需通过数组'number [i]'记录'i'放入的数字很容易找到负圆队列。

可以证明，如果一个点被放入队列超过|P|(points number)次，图中就有一个负圆。所以可以添加：

number[v]++; if (number[v] > |P|) return -1;

负圆图中的最短距离没有意义。因此对于大多数情况，您只需要在找到它的同时打印一些东西。

于 2016-08-24T03:34:11.343 回答