最短路径之Dijkstra算法

学习数据结构与算法
2021-05-17 14:29 · 阅读时长8分钟
小课

Dijkstra算法是一个单源最短路径算法,也就是一次只能求从一个顶点到其余各顶点的最短路径,不支持存在负权的图,使用数组实现的时间复杂度是O(V2),使用优先队列实现的时间复杂度是O((V+E)LogV),V是顶点的数量,E是边的数量。

主要思路是从起点开始,采用贪心算法的策略,每次选取距离起始点最近且未访问过的顶点v,然后比较其它顶点原来与起点的距离,和以顶点v作为中转点的之后该点与起点的距离,如果比原来的距离短,则更新。

首先定义一个数组distance,数组中第i个元素代表起始点到第i个顶点当前的最短距离,我们通过不断的寻找最短的中转点来更新这个数组,如下所示

加载中...

上面的示例,使用Dijkstra算法求最短路径的两种代码实现

加载中...
最短路径算法Dijkstra