本文主要是介绍C#，图论与图算法，任意一对节点之间最短距离的弗洛伊德·沃肖尔（Floyd Warshall）算法与源程序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、弗洛伊德·沃肖尔算法
Floyd-Warshall算法是图的最短路径算法。与Bellman-Ford算法或Dijkstra算法一样，它计算图中的最短路径。然而，Bellman Ford和Dijkstra都是单源最短路径算法。这意味着他们只计算来自单个源的最短路径。另一方面，Floyd Warshall计算输入图中每对顶点之间的最短距离。
假设你有5个朋友：比利、珍娜、卡西、艾丽莎和哈里。你知道有几条路连接他们的一些房子，你知道这些路的长度。但是，弗洛伊德·沃沙尔可以利用你所知道的，并根据这些信息为你提供最佳路线。例如，看看下面的图表，它显示了从一个朋友到另一个朋友的路径以及相应的距离。
我们初始化解矩阵的第一步与输入图矩阵相同。然后，我们通过将所有顶点视为中间顶点来更新解矩阵。其思想是一个接一个地拾取所有顶点，并更新所有最短路径，其中包括拾取的顶点作为最短路径中的中间顶点。当我们选取顶点数 k 作为中间顶点时，我们已经考虑了顶点{0，1，2，..k-1}作为中间顶点。对于源顶点和目标顶点的每一对(I，j)，都有两种可能的情况。 1) k 在从 I 到 j 的最短路径中不是中间顶点，我们保持 dist[i][j]的值不变。 2) k 是从 I 到 j 的最短路径中的中间顶点，我们将 dist[i][j]的值更新为 dist[I][k]+dist[k][j]if dist[I][j]>dist[I][k]+dist[k][j] 下图显示了以上
这篇关于C#，图论与图算法，任意一对节点之间最短距离的弗洛伊德·沃肖尔（Floyd Warshall）算法与源程序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
