Bellman-Ford 改进：有效吗？

Question

我正在尝试改进 Bellman-Ford 算法的性能，我想知道改进是否正确。

我运行松弛部分不是 V-1 而是 V 次，我得到了一个布尔变量，如果在外循环迭代期间发生任何松弛，则设置 true 。如果在 n 没有放松。 n <= V 的迭代，它 return 从具有最短路径的循环开始，但如果它在 n = V 迭代时放松，这意味着我们有一个负循环。

我认为它可能会改善运行时间，因为有时我们不必迭代 V-1 次来找到最短路径，我们可以 return 更早，而且它也是比用另一个代码块检查循环更优雅。

AdjacencyListALD graph;

int[] distTo;
int[] edgeTo;

public BellmanFord(AdjacencyListALD g)
{
    graph = g;
}

public int findSP(int source, int dest)
{

    // initialization

    distTo = new int[graph.SIZE];
    edgeTo = new int[graph.SIZE];

            for (int i = 0;i<graph.SIZE;i++)
            {
                distTo[i] = Integer.MAX_VALUE;
            }

            distTo[source] = 0;

    // relaxing V-1 times + 1 for checking negative cycle = V times

    for(int i = 0;i<(graph.SIZE);i++)
    {
        boolean hasRelaxed=false;

        for(int j = 0;j<graph.SIZE;j++)
        {
            for(int x=0;x<graph.sources[j].length;x++)
            {
                int s = j;
                int d = graph.sources[j].get(x).label;
                int w = graph.sources[j].get(x).weight;

                if(distTo[d] > distTo[s]+w)
                {
                    distTo[d] = distTo[s]+w;
                    hasRelaxed = true;                      
                }
            }
        }
        if(!hasRelaxed)
            return distTo[dest];

    }
    System.out.println("Negative cycle detected");
    return -1;


}

Answer 1

关于测试需求的好评。这是一个给定的。但它没有解决根本问题，OP 对 Bellman-Ford 的修改是否构成对算法 的改进。答案是，是的，正如 G. Bach 在评论中指出的那样，这实际上是一个众所周知的改进。

OP 的观察是，如果在任何松弛迭代中没有任何松弛，那么后续迭代将不会有任何变化，因此我们可以停止。完全正确。分配给顶点的值没有外部影响。唯一更新这些值的是松弛步骤本身。如果它在任何迭代中发现无事可做，那么有事可做 就不可能从以太中具体化。因此我们可以终止。

这不会影响算法的复杂性，也不会帮助处理最坏情况的图表，但它可以减少实践中的实际运行时间。

至于运行再放宽一次（|V| 次而不是通常的 |V|-1 次），这只是说明 检查的另一种方式松弛步骤之后的负循环。这只是另一种说法，当我们以运行 |V|-1 次松弛迭代终止时，我们需要查看是否仍然可以计算出任何改进，这揭示了一个负循环。

底线：OP 的方法是合理的。现在，是的，测试代码。

Bellman-Ford 改进：有效吗？

Bellman-Ford improvement: does it work?

java

algorithm

bellman-ford