C#,图论与图算法,任意一对节点之间最短距离的弗洛伊德·沃肖尔(Floyd Warshall)算法与源程序

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



http://www.chinasem.cn/article/841166

相关文章

C#使用HttpClient进行Post请求出现超时问题的解决及优化

《C#使用HttpClient进行Post请求出现超时问题的解决及优化》最近我的控制台程序发现有时候总是出现请求超时等问题,通常好几分钟最多只有3-4个请求,在使用apipost发现并发10个5分钟也... 目录优化结论单例HttpClient连接池耗尽和并发并发异步最终优化后优化结论我直接上优化结论吧,

C#使用yield关键字实现提升迭代性能与效率

《C#使用yield关键字实现提升迭代性能与效率》yield关键字在C#中简化了数据迭代的方式,实现了按需生成数据,自动维护迭代状态,本文主要来聊聊如何使用yield关键字实现提升迭代性能与效率,感兴... 目录前言传统迭代和yield迭代方式对比yield延迟加载按需获取数据yield break显式示迭

c# checked和unchecked关键字的使用

《c#checked和unchecked关键字的使用》C#中的checked关键字用于启用整数运算的溢出检查,可以捕获并抛出System.OverflowException异常,而unchecked... 目录在 C# 中,checked 关键字用于启用整数运算的溢出检查。默认情况下,C# 的整数运算不会自

C#实现获得某个枚举的所有名称

《C#实现获得某个枚举的所有名称》这篇文章主要为大家详细介绍了C#如何实现获得某个枚举的所有名称,文中的示例代码讲解详细,具有一定的借鉴价值,有需要的小伙伴可以参考一下... C#中获得某个枚举的所有名称using System;using System.Collections.Generic;usi

C# 读写ini文件操作实现

《C#读写ini文件操作实现》本文主要介绍了C#读写ini文件操作实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录一、INI文件结构二、读取INI文件中的数据在C#应用程序中,常将INI文件作为配置文件,用于存储应用程序的

C#实现获取电脑中的端口号和硬件信息

《C#实现获取电脑中的端口号和硬件信息》这篇文章主要为大家详细介绍了C#实现获取电脑中的端口号和硬件信息的相关方法,文中的示例代码讲解详细,有需要的小伙伴可以参考一下... 我们经常在使用一个串口软件的时候,发现软件中的端口号并不是普通的COM1,而是带有硬件信息的。那么如果我们使用C#编写软件时候,如

C#中图片如何自适应pictureBox大小

《C#中图片如何自适应pictureBox大小》文章描述了如何在C#中实现图片自适应pictureBox大小,并展示修改前后的效果,修改步骤包括两步,作者分享了个人经验,希望对大家有所帮助... 目录C#图片自适应pictureBox大小编程修改步骤总结C#图片自适应pictureBox大小上图中“z轴

使用C#代码计算数学表达式实例

《使用C#代码计算数学表达式实例》这段文字主要讲述了如何使用C#语言来计算数学表达式,该程序通过使用Dictionary保存变量,定义了运算符优先级,并实现了EvaluateExpression方法来... 目录C#代码计算数学表达式该方法很长,因此我将分段描述下面的代码片段显示了下一步以下代码显示该方法如

C#实现WinForm控件焦点的获取与失去

《C#实现WinForm控件焦点的获取与失去》在一个数据输入表单中,当用户从一个文本框切换到另一个文本框时,需要准确地判断焦点的转移,以便进行数据验证、提示信息显示等操作,本文将探讨Winform控件... 目录前言获取焦点改变TabIndex属性值调用Focus方法失去焦点总结最后前言在一个数据输入表单

基于C#实现PDF文件合并工具

《基于C#实现PDF文件合并工具》这篇文章主要为大家详细介绍了如何基于C#实现一个简单的PDF文件合并工具,文中的示例代码简洁易懂,有需要的小伙伴可以跟随小编一起学习一下... 界面主要用于发票PDF文件的合并。经常出差要报销的很有用。代码using System;using System.Col