侧边栏壁纸
  • 累计撰写 247 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

最短路径及实现算法(一):迪杰斯特拉算法(Dijkstra)

kaixindeken
2021-04-23 / 0 评论 / 0 点赞 / 95 阅读 / 957 字

最短路径

在日常生活中,我们经常面临路径选择的问题,比如从杭州到北京,可以选择汽车、火车、飞机,甚至还可以坐公交车(这不是笑话,最近网上就流传一个从杭州回临沂,转了 35 班公交车,行程 660 多公里,历时 7 天的神奇春运回家路),对于不同的选择,意味着不同的路径,不同的路径意味着不同的成本,这个成本有时间成本,也有经济成本,不差钱的可以选择时间成本低的,比如坐飞机,经济不那么宽裕却有时间的,可以做公交车,我们把杭州和北京看作图上的两个顶点(中间可能会经过其它城市,即多个顶点),把时间成本或者经济成本看作权重,那么从杭州到北京的路径规划就可以抽象为今天我们要分享的话题 —— 图的最短路径问题。

对于带权重的网图来说,所谓最短路径,指的是两个顶点之间经过的边上权值之和最小的路径,我们将第一个顶点叫做起点,最后一个顶点叫做终点。

迪杰斯特拉算法

迪杰斯特拉(Dijkstra)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。

我们以下面这个无向图为例:

1.png

通过迪杰斯特拉算法计算最短路径,需要指定起点,我们用 S 表示图的所有顶点集合,U 表示起点外的其它顶点集合,顶点到自身的距离为 0,到相邻顶点距离为相应边的权值,到不相邻顶点的距离为无穷大(∞)。每一次从 U 中找出路径最短的顶点,并将其加入到 S 中,然后,更新 U 中的剩余顶点和顶点对应的路径,重复该操作,直到遍历完所有顶点:

1.png

复杂度分析

对于计算某个顶点到任意其它顶点需要两层嵌套循环,对应的时间复杂度是 O(n2),如果要计算所有顶点的最短路径,则还要在外面嵌套一层循环,对应的时间复杂度是 O(n3)。当顶点很多,路径很复杂时,对时间开销不小。

0

评论区