本文主要是介绍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)算法与源程序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!