当前位置:鱼C工作室 >数据结构和算法 > 查看文章

最短路径(迪杰斯特拉算法)- 数据结构和算法64

最短路径(迪杰斯特拉算法)

 

让编程改变世界

Change the world by program


 

最短路径(迪杰斯特拉算法)

 

我们时常会面临着对路径选择的决策问题,例如在中国的一些一线城市如北京、上海、广州、深圳等,一般从A点到到达B点都要通过几次地铁、公交的换乘才可以到达。

 

有些朋友想用最短对的时间,有些朋友想花最少的金钱,这就涉及到不同的方案,那么如何才能最快的计算出最佳的方案呢?

最短路径求法

最短路径求法

 

在网图和非网图中,最短路径的含义是不同的。

  • 网图是两顶点经过的边上权值之和最少的路径。
  • 非网图是两顶点之间经过的边数最少的路径。

 

我们把路径起始的第一个顶点称为源点,最后一个顶点称为终点。

 

关于最短路径的算法,我们会介绍两种:

  • 迪杰斯特拉算法(Dijkstra)
  • 弗洛伊德算法(Floyd)

 

求V0到V8的最短路径

迪杰斯特拉算法

迪杰斯特拉算法

 

你找到了吗

迪杰斯特拉算法

迪杰斯特拉算法

 

迪杰斯特拉算法原理

 

好了,我想你大概明白了,这个迪杰斯特拉算法是如何工作的。

它并不是一下子就求出了V0到V8的最短路径,而是一步步求出它们之间顶点的最短路径,过程中都是基于已经求出的最短路径的基础上,求得更远顶点的最短路径,最终得到你要的结果。

 

如果还不大明白,没关系,现在小甲鱼带着大家一起来解读代码,把自己模拟成计算机,模拟代码的运行,再次去理解它的思想。

代码下载:dijkstra.c


为您推荐

报歉!评论已关闭.