algorithm - 贝尔曼福特算法

Question

我知道 Bellman-Ford 算法最多需要 |V| - 如果图形不包含负权重循环，则进行 1 次迭代以找到最短路径。有没有办法修改 Bellman-Ford 算法，使其在 1 次迭代中找到最短路径？

Answer 1

不，Bellman-Ford 的最坏情况运行时间是 O(E*V)，这是因为需要在图上迭代 V-1 次。然而，我们实际上可以通过使用基于队列的 bellman-ford 变体将 Bellman-Ford 的运行时间提高到 O(E+V)。

这是基于队列的 Bellman-Ford 实现。代码灵感来自书网站Algorithms, 4th edition, Robert Sedgewick 和 Kevin Wayne

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;
            }
        }
    }
}

该算法的最坏情况运行时间仍然是 O(E*V)，但在该算法中，实际运行时间通常为 O(E+V)。