最短路径算法

在图中两个顶点之间的路径

最短路径问题来自于实际生活中
在一个地区中,各个城市之间公路网连接。
知道n个城市和想通的公路和距离,找从A城市到B城市最近的一条道路。

在图中两个顶点之间的路径,下图求出a点到b点的最短路径的过程。

从a出发,到终点b,对上图gif解析如下。

  • ①到②的距离为7,①到③的距离为9,①到⑥的距离为14。out①,最短距离是到②,下一个判断②
  • ②到③的距离为10,则从①到②再到③的距离为10+7 17>①到③的距离为9。②到④的距离15,①到④的距离为22。out②,最短距离是到③,下一判断③
  • ③到④的距离为11,则从①到③再到④的距离20 < 从①到②再到④的距离22,更新到④的距离为20。 ③到⑥的距离为2,则从①到③再到⑥的距离11 < 从①到⑥的距离14,更新到⑥的距离为11。 out③,最短距离是到⑥,下一个判断⑥
  • ⑥到⑤(为终点b)的距离为9,即最终为从①到⑥再到⑤,out⑥。

xpisme wechat
微信号