对于有向边权图，Bellman Ford算法无法计算出最短路径

Question

我最近正在理解最短路径算法，当我遇到下面的问题在书算法，第四版，罗伯特·塞奇威克和凯文·韦恩。

假设我们通过在EdgeWeightedDigraph中为EdgeWeightedGraph中的每个边创建两个DirectedEdge对象(每个方向一个)，然后使用Bellman-Ford算法，将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;
            }
        }
    }
}

我在纸上尝试了很多例子，但我无法找到有向图生成新的负循环的场景，仅仅通过将一条边转换成相反方向的两条边。我假设在未加权无向边加权图中不存在预先存在的负环

Answer 1

你的算法&代码没有问题。它能给出无负圆图上的最短距离。通过数组'number[i]'记录'i'放入队列的数字，可以很容易地找到负循环

可以证明，如果将一个点放入队列超过| p |(点数数)次，则图中存在一个负圆。所以你可以加上:

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

负圆图中的最短距离没有意义。所以在大多数情况下，你只需要在找到它的时候打印一些东西。