漫画:如何求图的最短路径? | 技术头条

栏目: IT资讯 · 发布时间: 5年前

内容简介:作者 | 程序员小灰

漫画:如何求图的最短路径? | 技术头条

漫画:如何求图的最短路径? | 技术头条

作者 | 程序员小灰

本文经授权转载自 程序员 小灰(ID:chengxuyuanxiaohui)

漫画:如何求图的最短路径? | 技术头条

漫画:如何求图的最短路径? | 技术头条

—————  第二天  —————

漫画:如何求图的最短路径? | 技术头条

漫画:如何求图的最短路径? | 技术头条

漫画:如何求图的最短路径? | 技术头条

漫画:如何求图的最短路径? | 技术头条

漫画:如何求图的最短路径? | 技术头条

漫画:如何求图的最短路径? | 技术头条

小灰的思路如下:

第一步,利用迪杰斯特拉算法的距离表,求出从顶点A出发,到其他各个顶点的最短距离:

漫画:如何求图的最短路径? | 技术头条

第二步,继续使用迪杰斯特拉算法,求出从顶点B出发,到其他各个顶点的最短距离。

第三步,从顶点C出发,到各个顶点的最短距离。

第四步,从顶点D出发......

.......

就像这样,一直遍历到顶点G。

这个思路的时间复杂度是多少呢?

假如图中有n个顶点,如果不考虑堆优化,一次迪杰斯特拉算法的时间复杂度是O(n^2)。所以,把每一个顶点都计算一遍,总的时间复杂度是O(n^3)。

漫画:如何求图的最短路径? | 技术头条

漫画:如何求图的最短路径? | 技术头条

漫画:如何求图的最短路径? | 技术头条

漫画:如何求图的最短路径? | 技术头条

漫画:如何求图的最短路径? | 技术头条

漫画:如何求图的最短路径? | 技术头条

漫画:如何求图的最短路径? | 技术头条

漫画:如何求图的最短路径? | 技术头条

漫画:如何求图的最短路径? | 技术头条

漫画:如何求图的最短路径? | 技术头条

漫画:如何求图的最短路径? | 技术头条

举一个栗子:

漫画:如何求图的最短路径? | 技术头条

上图的顶点A和顶点C没有直接相连的边,它们之间的直接距离是无穷大。

如果以B作为“中继顶点”,此时A到C的最短路径就是A-B-C,最短距离是3+2=5。

漫画:如何求图的最短路径? | 技术头条

再举一个栗子:

漫画:如何求图的最短路径? | 技术头条

上图的顶点A和顶点C直接相连,距离是6。但是存在一条“迂回”路径A-B-C,距离是3+2=5<6。

所以,经过中继顶点B,从A到C的最短距离可以是5。

漫画:如何求图的最短路径? | 技术头条

下面我们来看一看Floyd算法的详细步骤。

1.要实现Floyd算法,首先需要构建带权图的邻接矩阵:

漫画:如何求图的最短路径? | 技术头条

在邻接矩阵当中,每一个数字代表着从某个顶点到另一个顶点的直接距离,这个距离是没有涉及到任何中继顶点的。

2.此时假定只允许以顶点A作为中继顶点,那么各顶点之间的距离会变成什么样子呢?

B和C之间的距离原本是无穷大,此时以A为中继,距离缩短为AB距离+AC距离=

5+2=7。

更新对应矩阵元素(橙色区域代表顶点A到其他顶点的临时距离):

漫画:如何求图的最短路径? | 技术头条

3.接下来以顶点A、B作为中继顶点,那么各顶点之间的距离会变成什么样子呢?

A和D之间的距离原本是无穷大,此时以B为中继,距离缩短为AB距离+BD距离=5+1=6。

A和E之间的距离原本是无穷大,此时以B为中继,距离缩短为AB距离+BE距离=5+6=11。

更新对应矩阵元素(橙色区域代表顶点B到其他顶点的临时距离):

漫画:如何求图的最短路径? | 技术头条

4.接下来以顶点A、B、C作为中继顶点,那么各顶点之间的距离会变成什么样子呢?

A和F之间的距离原本是无穷大,此时以C为中继,距离缩短为AC距离+CF距离=2+8=10。

更新对应矩阵元素(橙色区域代表顶点C到其他顶点的临时距离):

漫画:如何求图的最短路径? | 技术头条

以此类推,我们不断引入新的中继顶点,不断刷新矩阵中的临时距离。

最终,当所有顶点都可以作为中继顶点时,我们的距离矩阵更新如下:

漫画:如何求图的最短路径? | 技术头条

此时,矩阵中每一个元素,都对应着某顶点到另一个顶点的最短距离。

漫画:如何求图的最短路径? | 技术头条

漫画:如何求图的最短路径? | 技术头条

为什么这么说呢?让我们回顾一下动态规划的两大要素:

问题的初始状态
问题的状态转移方程式

对于寻找图的所有顶点之间距离的问题,初始状态就是顶点之间的直接距离,也就是邻接矩阵。

而问题的状态转移方程式又是什么呢?

假设新引入的中继顶点是n,那么:

顶点i 到 顶点j 的新距离 = Min(顶点i 到 顶点j 的旧距离,顶点i 到 顶点n 的距离+顶点n 到 顶点j 的距离)

漫画:如何求图的最短路径? | 技术头条

漫画:如何求图的最短路径? | 技术头条

漫画:如何求图的最短路径? | 技术头条

【END】

漫画:如何求图的最短路径? | 技术头条

作为码一代,想教码二代却无从下手:

听说少儿编程很火,可它有哪些好处呢?

孩子多大开始学习比较好呢?又该如何学习呢?

最新的编程教育政策又有哪些呢?

下面给大家介绍CSDN新成员: 极客宝宝(ID: geek_baby)

戳他了解更多↓↓↓

漫画:如何求图的最短路径? | 技术头条

 热 文推 荐 

  手机基带芯片激荡 30 年!

硬核追星!杨超越杯决赛是些啥编程项目?

前端代码的整洁之道 | 技术头条

☞  异构计算=未来?一文带你秒懂3大主流异构

☞ 她说:为啥程序员都特想要机械键盘?这答案我服!

System.out.println("点个在看吧!");
console.log("点个在看吧!");
print("点个在看吧!");
printf("点个在看吧!\n");
cout << "点个在看吧!" << endl;
Console.WriteLine("点个在看吧!");
Response.Write("点个在看吧!");
alert("点个在看吧!")
echo "点个在看吧!"

你点的每个“在看”,我都认真当成了喜欢


以上所述就是小编给大家介绍的《漫画:如何求图的最短路径? | 技术头条》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

数据驱动:从方法到实践

数据驱动:从方法到实践

桑文锋 / 电子工业出版社 / 2018-3 / 49

本书是从理论到实践的全面且细致的企业数据驱动指南,从作者的百度大数据工作说起,完整还原其从零到一构建百度用户行为大数据处理平台经历。详解大数据本质、理念与现状,围绕数据驱动四环节——采集、建模、分析、指标,深入浅出地讲述企业如何将数据驱动方案落地,并指出数据驱动的价值在于“数据驱动决策”、“数据驱动产品智能”。最后通过互联网金融、电子商务、企业服务、零售四大行业实践,从需求梳理、事件指标设计、数据......一起来看看 《数据驱动:从方法到实践》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具