寻找最短路径算法教程3：Floyd Warshall算法和实现简介-ProDeveloperTutorial.com

在本教程中，我们将学习Floyd warshall算法。此算法用于查找从所有顶点到其他每个顶点的最短路径。这是3^rd键入以查找源节点到目标节点之间的最短路径。

我们将通过使用动态编程方法解决此问题。

在研究Floyd Warshall算法之前，让我们回顾一下前面的2种算法。

Dijkstra的算法：当我们需要查找从一个节点到所有其他节点/顶点的最短路径时，使用此算法。
贝拉姆·福特算法：该算法用于查找从一个节点到所有其他节点的最短路径，允许-ve边。
Floyd Warshall算法：此算法用于查找从所有顶点到其他每个顶点的所有最短路径。这里也允许–ve值的边缘。

让我们借助示例来了解Floyd Warshall算法的工作原理。

如前所述，该算法使用动态编程来得出解决方案。因此，正如我们在前一章中所看到的，DP方法使用记忆技术，将问题分为简单的子问题，并解决这些子问题以得出解决方案。

考虑下图：

从上图计算距离矩阵。

在构造距离矩阵时，如果2个节点之间存在直接边缘，则写入该值。如果没有直接路径，则将其设置为Infinity。

下面是距离矩阵。我们将其命名为“ D0”。

从上面的矩阵中可以看到，对角线值始终为零。这是因为从同一个节点到源的成本为零。

由于有4个顶点，我们需要创建4个矩阵表。每个节点一个。因此，最后，我们得到了从任何顶点到任何其他顶点的最短路径。

当我们使用DP方法时，我们将利用先前生成的矩阵并基于该矩阵计算值。

现在，让我们编写D1矩阵。对于D1矩阵，我们取1^ST行和1^STD0矩阵中的列。初始D1矩阵如下：

为了填充D1矩阵，我们将以D0矩阵作为参考。

现在，我们将剩下的空单元格莳萝。为了填补这一点，我们使用以下两个步骤：

检查是否存在从源顶点到目标顶点的直接路径。如果有，请记录下来。

检查是否有一条通过当前我们正在使用的节点的路径。如果有路径，请记下通过当前节点的总距离。

然后取上述2个值的最小值并填写矩阵。

对于我们当前的矩阵D1，我们必须填充[b，c]和[b，d]。这里我们将D0矩阵作为参考并填充D1矩阵。

[b，c] =>检查从D0矩阵是否有直接路径。不，那里没有。现在检查是否存在包含“ a”（即“ b-> a, a -> c”.

有，成本为“ 7 -1 = 6”。这小于INF。

更新矩阵

[b，d] =检查是否存在从“ b”到“ d”的直接路径。有一个路径，值为2。

检查是否存在通过“ a”的路径。即“ b-> a, a -> d”.

7 + INF = INF。

当INF大于2时，我们选择min元素，即2。

因此，更新矩阵2。

同样，我们对[c，b]和[c，d]执行此操作。

[c至b]

直接路径值为= 3

通过“ a” => c -> a + a -> b

INF + 4 = INF

因此更新3。

[c到d]

直接路径值为INF。

通过“ a”是c-> a + a -> d

INF + INF
INF

因此INF。以下是更新的值：

同样，我们针对[d，b] [d，c]

[D b]

直接路径值为INF

通过“ a”是=> d -> a + a -> b

INF + 4
INF

更新INF

[d，c]

直接路径值= 1

通过“ a”是=> d-> a + a-> c

INF -1
INF

因此，Min（1，INF）。更新1。

因此，D1表现在已完成。结果如下：

现在，从上述步骤中，我们可以得出公式以找出最小成本。

DK[i, j] = min [ Dk-1[i, j], Dk-1[i, k] + Dk-1[k, j] ]

其中k是节点号，D是距离矩阵。

现在为2^nd节点。这里K将为2。

现在借助D1矩阵构造D2矩阵。

现在我们取2^nd行和2^nd将列从D1矩阵复制到D2矩阵，如下所示：

同样，就像在D1矩阵中所做的一样，我们从“ b”中获取直接路径或通过路径的最小值，然后选择最小值。这里我们将借助D1矩阵作为参考。

[a，c]

直接路径值= -1

通过“ b”路径=> a -> b + b ->c

4 + 6
10

当min为-1时，选择-1。

[广告]

直接路径值= INF

通过路径值=“ a-> b” +“ b-> d”

4 + 2
6

最小值[INF，6] = 6

[c，a]

直接路径= INF

通过“ b”路径=> “c->b” + “b -> a”

3 + 7
10

min [INF，10] = 10

[c，d]

直接路径= INF

通过“ b”路径=> “c->b” + “b->d”

3 + 2
5

min [INF，5] = 5

[d，a]

直接路径= INF

通过“ b”路径= “d->b” + “b ->a”

INF + 7
INF

[d，c]

直接路径= 1

通过路径“ d->b” + “b->c”

INF + 6
INF

min（INF，1）= 1

因此，“ D2”矩阵如下

现在我们将构建“ D3”矩阵。通过从D2矩阵中获取值，使第3行和第3列恒定。结果矩阵如下：

同样，我们像上面的矩阵一样进行计算。现在，via元素将为“ c”。

[a，b] => Direct path = 4,

通过“ c”路径=> “a->c” + “c->b”
-1 + 3 = 2

分钟（4，2）= 2

[a，d] => Direct path = 6,

通过“ c”路径=> “a->c” + “c->d”
-1 + 5 = 6

分钟（6，4）= 4

[b，a] => Direct path = 7,

通过“ c”路径=> “b->c” + “c->a”
6 + 10 = 16

分钟（16，7）= 7

[b，d] => Direct path = 2,

通过“ c”路径=> “b->c” + “c->d”
6 + 5 = 11

分钟（11，2）= 2

[d，a] => 直接路径= INF,

通过“ c”路径=> “d->c” + “c->a”
1 + 10 = 11

min（INF，11）= 11

[d，b] => 直接路径= INF,

通过“ c”路径=> “d->c” + “c->b”
1 + 3 = 4

分钟（INF，4）= 4

所以最终矩阵如下

同样，我们将构建“ D4”矩阵。首先，我们将复制4^日行和4^日“ D3”矩阵中的列，如下所示：

我们将像上面那样计算，via元素将为“ d”。

[a，b] => Direct path = 2,

通过“ d”路径=> “a->d” + “d->b”
4 + 4 = 8

分钟（2，8）= 2

[a，c] => Direct path = -1,

通过“ d”路径=> “a->d” + “d->c”
4 +1 = 5

分钟（-1，5）= -1

[b，a] => Direct path = 7,

通过“ d”路径=> “b->d” + “d->a”
2 + 11 = 13

分钟（7，13）= 7

[b，c] => Direct path = 6,

通过“ d”路径=> “b->d” + “d->c”
2 +1 = 3

分钟（6，3）= 3

[c，a] => 直接路径= 10,

通过“ d”路径=> “c->d” + “a->b”
5 + 11 = 16

分钟（10，16）= 10

[c，b] => Direct path = 3,

通过“ d”路径=> “c->d” + “d->b”
5 + 4 = 9

分钟（3，9）= 3

最终，我们完成了所有4个矩阵的计算。矩阵“ D4”将成为最终矩阵，如下所示：

上面的矩阵将给出从任何节点到任何其他顶点的最短路径。

Floyd Warshall在C ++中的实现

#include<stdio.h>
#define V 4
#define INF 99999
 
void printSolution(int dist[][V]);
 
void floydWarshall (int graph[][V])
{
    int dist[V][V], i, j, k;
     for (i = 0; i < V; i++)
        for (j = 0; j < V; j++)
            dist[i][j] = graph[i][j];
 
    for (k = 0; k < V; k++)
    {
        for (i = 0; i < V; i++)
        {
            for (j = 0; j < V; j++)
            {
                if (dist[i][k] > dist[k][j] + dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
 
    printSolution(dist);
}
 
void printSolution(int dist[][V])
{
    printf ("The shortest distances"
            " between every pair of vertices \n");
    for (int i = 0; i < V; i++)
    {
        for (int j = 0; j < V; j++)
        {
            if (dist[i][j] == INF)
                printf("%7s", "INF");
            else
                printf ("%7d", dist[i][j]);
        }
        printf("\n");
    }
}
 
int main()
{
    int graph[V][V] = { {0,   5,  INF, 10},
                        {INF, 0,   3, INF},
                        {INF, INF, 0,   1},
                        {INF, INF, INF, 0}
                      };
 
    floydWarshall(graph);
    return 0;
}

进一步阅读：

AJ关于DS和算法的权威指南。单击此处以学习算法和数据结构教程的完整列表。 85多个章节可供学习。

该网站上可用的教程列表：

C编程20+章	C ++编程80+章
100多个编码问题	数据结构和算法85+章
系统设计20+章	Shell脚本编写12章
4g LTE 60+章节	最常见的编码问题
5G NR 50+章	Linux系统编程20+章

上一篇文章

Floyd Warshall在C ++中的实现

进一步阅读：

该网站上可用的教程列表：

关于作者

前开发者教程