有向图上的单源最短路径问题基于Dijkstra算法

问题表述为：在给定一个没有负权值的有向图中，并选取其中一个节点作为出发点（source），计算从该出发点到其他各节点的最短路径及其长度的问题。通常采用Dijkstra算法来解决这一类型的问题。

给定一个图中顶点的数量为n（记作n），则对于剩下的n-1个顶点中的每一个都需要计算源顶点src到这些顶点的最短路径。Dijkstra算法的核心理念在于采用贪心策略逐步确定最短路径的过程：首先确定从src出发到达离它最近的那个顶点；其次确定从src出发到达次近的那个顶点；接着找到第三近的那个顶点；依此类推直至完成所有目标顶点之间的距离计算。以下将通过具体实例阐述该算法及其运行原理。

如图所示（该图源自《数据结构预（用面向对象方法与C++语言描述）（第2版）》殷人昆主编清华大学出版社），求顶点0到其余各点的最短路径及其路径长度。

直接到达

立即到达

立即到达

从定点0出发可直接抵达点1、3及4；其余无法直接通达的节点，则将其与定点0之间的距离设为无穷大；因此，在所有可能的路径中，最短的路径即定点0至节点1的距离仅为10单位长度。进一步分析可知，在所有可能存在的从定点0到