该算法以自下而上的方式计算最短路径。它首先计算最多具有一条边的路径的最短距离。然后,它计算最多具有2条边的最短路径,依此类推。
在外部循环的第i次迭代之后,将计算最多具有i条边的最短路径。在任何简单路径中,最多可以有|V|-1条边,这就是为什么外部循环运行|v|-1次的原因。假设没有负权重环,那么我们的想法是,如果我们已经计算出至多具有i条边的最短路径,则对所有边进行迭代保证给出最多(i+1)条边的最短路径。
让我们通过以下示例图形来理解算法。 这些图像来自此来源。
假设给定的源顶点是0。将所有距离初始化为无穷大,除了与源本身的距离。图中总共有5个顶点,因此所有边必须处理4次。
如果边的顺序是(AB),(BE),(ED),(DC),(AC),(BC),(DB),(BD)等,则仅在一次迭代中,它将计算具有甚至2-3条边的最短路径,这与“首先计算最多具有一条边的最短路径。然后,它计算最多具有2条边的最短路径,以此类推。在外部循环的第i次迭代之后,计算了最多具有i条边的最短路径”这一说法相矛盾。因此,通过改变边的顺序,这个语句将被证明是错误的。
让我们通过以下示例图形来理解算法。这些图像来自此来源。
假设给定的源顶点是0。将所有距离初始化为无穷大,除了与源本身的距离。图中总共有5个顶点,因此所有边必须处理4次。 让我们按照以下顺序处理所有边缘:(B,E),(D,B),(B,D),(A,B),(A,C),(D,C),(B,C),(E,D)。当第一次处理所有边缘时,我们得到以下距离。第一行显示初始距离。第二行显示处理(B,E),(D,B),(B,D)和(A,B)后的距离。第三行显示处理(A,C)后的距离。第四行显示处理(D,C),(B,C)和(E,D)后的距离。
![enter image description here](https://istack.dev59.com/Cfidf.webp)
BD
和DB
。 - Codor