Bellman Ford算法无法计算有向边加权图的最短路径-Java 学习之路

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

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

下面是我的code实现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;
            }
        }
    }
}

我在纸上尝试了很多例子，但是我无法找到生成的有向图会在其中产生新的负循环的场景，只需将边缘转换为相反方向的两条边 . 我假设未加权的无向边加权图中没有预先存在的负循环 .

1 回答

-1

你的算法和代码没有问题 . 它可以在没有负圆的图形中给出最短距离 . 它's easy to find out negative circle only by a array ' number [i]'record the number that 'i' is put into the queue.

可以证明，如果一个点被放入队列中超过| P |（点数）次，则图中有一个负圆 . 所以你可以添加：

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

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

回复于 2024-04-30T02:54:29+08:00

Bellman Ford算法无法计算有向边加权图的最短路径

1 回答

相关问题