dijkstra最短路径算法

Dijkstra最短路径算法是一种用于计算带权有向图中单源最短路径的贪心算法。它通过构建一个候选最短路径的集合，逐步扩展这个集合，从而找到从源节点到所有其他节点的最短路径。

具体实现步骤如下：

1. 初始化：将源节点标记为已访问，将源节点到各个节点的距离设为无穷大（除了源节点到自身为0）。

2. 选取一个与源节点距离最近的未访问节点，并将其标记为已访问。

3. 对于该节点的每个相邻节点，计算源节点到该相邻节点的距离（即经过该节点的距离），并更新源节点到该节点的最短距离。

4. 重复步骤2和3，直到所有节点都被访问过或者没有与源节点相连通的节点。

在实现Dijkstra算法时，通常使用一个优先队列来存储候选最短路径的集合，并按照距离从小到大的顺序进行排序。这样可以保证每次选取的节点都是目前距离最短的节点，从而提高运行效率。