2023年7月30日发(作者：)

信息学奥赛培训讲义 最短路径算法——Dijkstra算法

最短路径算法——Dijkstra算法

一、最短路径问题

最短路问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。

最短路径算法的选择与实现是通道路线设计的基础,最短路径算法是计算机科学与地理信息科学等领域的研究热点,很多网络相关问题均可纳入最短路径问题的范畴之中。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。

在带权图（即网络）G=（V,E）中，若顶点vi，vj是图G的两个顶点，从顶点vi到vj的路径长度定义为路径上各条边的权值之和。从顶点vi到vj可能有多条路径，其中路径长度最小的一条路径称为顶点vi到vj的最短路径。求最短路径具有很高的实用价值，在各类竞赛中经常遇到。一般有两类最短路径问题：一类是求从某个顶点（即源点）到其他顶点（即终点）的最短路径；另一类是求图中每一对顶点间的最短路径。

本讲主要讲述一种单源最短路径（Single source shortest path）算法——Dijkstra算法，用于解决非负权有向图的单源最短路径问题。

二、Dijkstra算法

2.1 Dijkstra算法

Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率偏低。

Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。

- 1 - 信息学奥赛培训讲义 最短路径算法——Dijkstra算法

2.2 Dijkstra算法思想

对于图G=（V，E），假设（u，v）是E中的边，