贝尔曼-福特算法

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实现。代码灵感来源于booksite Algorithms，第四版，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）。