贝尔曼-福特改进：有效吗？

Question

我正在尝试改进贝尔曼-福特算法的性能，我想知道改进是否正确。

我运行松弛部分不是 V-1 而是 V 次，并且涉及一个布尔变量，true如果在外循环迭代期间发生任何松弛，则设置该变量。如果 n 处没有发生放松。当 n <= V 时，它从最短路径的循环中返回，但如果它在 n = V 迭代时放松，则意味着我们有一个负循环。

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

---

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的方法是合理的。现在，是的，测试代码。