八十七、探究最短路问题：Dijkstra算法

@Author：Runsen

在上次写道关于数据结构的图，图的算法的考点只有一个：最短路问题。

最短路问题

最短路问题（Shortest Path Problems）： 给定一个网络，网络的边上有权重，找一条从给定起点到给定终点的路径使路径上的边权重总和最小。

比如上图的：图中点1到点4的最短路径长度应为3（从1到2到4）。

最短路问题常用Dijkstra算法解决

Dijkstra算法

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

比如，上图Dijkstra算法就是不断地寻找开始节点到邻居节点的所有的路径，将最初的距离设置为最短距离，然后不断的更新节邻居节点的最短距离，直到最远的节点的最短距离求解出来的过程。

文字描述不清楚，看下面的动图。

将图上的顶点分为已访问visited和未访问node两个集合。

每次从visited向外拓展一个点，拓展规则是在可更新的点里是距离最小的。

我们还是以上面的图为例

文章来源: maoli.blog.csdn.net，作者：刘润森！，版权归原作者所有，如需转载，请联系作者。

原文链接：maoli.blog.csdn.net/article/details/114626400