本文主要是介绍Dijkstra算法及性能评估,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
二、Dijkstra 算法详解
写在前面:本文参考数据结构c语言版、july的blog——经典算法研究系列:二、Dijkstra 算法初探。
一、Dijkstra 算法的介绍
Dijkstra 算法,又叫迪科斯彻算法(Dijkstra),算法解决的是有向图中单个源点到其他顶点的最短路径问题。举例来说,如果图中的顶点表示城市,而边上的权重表示著城市间开车行经的距离,Dijkstra 算法可以用来找到两个城市之间的最短路径。
二、图文解析 Dijkstra 算法
ok,经过上文有点繁杂的信息,你还并不对此算法了如指掌,清晰透彻。没关系,咱们来幅图,就好了。请允许我再对此算法的概念阐述下,
Dijkstra算法是典型最短路径算法,用于计算一个节点到其他所有节点的最短路径。不过,针对的是非负值权边。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。[Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。]
ok,如下图,设A为源点,求A到其他各所有一一顶点(B、C、D、E、F)的最短路径。线上所标注为相邻线段之间的距离,即权值。
(注:此图为随意所画,其相邻顶点间的距离与图中的目视长度不能一一对等)
Dijkstra无向图
算法执行步骤如下表<
这篇关于Dijkstra算法及性能评估的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!