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

Question

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

我运行松弛部分不是V-1而是V次，并且我得到了一个涉及的布尔变量，如果在外循环的迭代过程中发生任何松弛，则将其设置为true。如果在n.迭代中没有发生松弛，其中n

我认为这可能会改善运行时，因为有时我们不必迭代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对贝尔曼-福特的修改是否构成对算法的改进。答案是，是的，正如巴赫在评论中指出的，这实际上是一个众所周知的进步。

OP的观察是，如果在任何松弛迭代中，没有任何东西松弛，那么在随后的迭代中就不会有任何变化，因此我们可以停止。绝对正确。对分配给顶点的值没有外部影响。唯一更新这些值的是松弛步骤本身。如果它在任何迭代中找不到任何可做的事情，那么就不可能有什么可做的事情从以太中实现。因此我们可以终止。

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

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

一句话：OP的方法是合理的。现在，是的，测试代码。