美文网首页
图-最短路径The shortest path, 2022-07

图-最短路径The shortest path, 2022-07

作者: Mc杰夫 | 来源:发表于2022-07-03 18:25 被阅读0次

(2022.07.04 Mon)
在介绍最短路径前引入加权图概念(weighted graph)：

图上的每个边伴随了一个数据标签，该数据成为边的权重(weight)，这样的图称为加权图。

对于有边e=(u, v)，我们用如下形式表示该边的权重w(u, v) = w(e)。

定义一个加权图的最短路径：

定义图G是一个加权图。(某条)路径P的长度/权重是路径P上每个边的权重之和。也就是，如果P=((v_0, v_1), (v_1, v_2), \cdots,(v_{k-1}, v_k))，则路径的长度可表示为w(P) = \sum_{i=0}^{k-1}w(v_i, v_{i+1})

图中顶点u到顶点v的举例，表示为d(u, v)是一个从u到v的最小长度路径(shortest path)，如果该路径存在的话。

为找到最短路径，可使用贪婪法，每次迭代中找出最优选择。

这里给出另一种最短路径算法，Dijkstra’s Algorithm。

Dijkstra’s Algorithm

Reference

1 Goodrich and etc., Data Structures and Algorithms in Python

相关文章

网友评论

      本文标题：图-最短路径The shortest path, 2022-07

      本文链接：https://www.haomeiwen.com/subject/ueadbrtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|图-最短路径The shortest path, 2022-07|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！