3

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

我运行放松部分不是 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;


}
4

1 回答 1

2

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

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

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

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

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

于 2015-11-09T13:25:41.107 回答