Dijkstra最短路径算法

Dijkstra最短路径算法是一种用于寻找图中两个顶点之间最短路径的经典算法。它由荷兰计算机科学家Edsger Dijkstra于1956年发明，主要用于解决有向无环图(DAG)的问题。该算法的工作原理基于贪心策略，通过逐步更新每个未访问节点的最短距离，直到找到目标节点。

以下是Dijkstra算法的主要步骤：
1. 初始化：标记源节点的距离为0，其他所有节点的距离设为无穷大，同时创建一个优先级队列（通常使用堆），将源节点入队。
2. 选择最小距离节点：从队列中取出当前距离最小的节点u。
3. 更新邻接节点：对于u的所有相邻节点v，如果通过u到达v的距离小于v当前的距离，则更新v的距离，并将v加入队列。
4. 继续迭代：重复步骤2和3，直到队列为空或者找到目标节点。
5. 结果：返回经过最少边或步数到达的目标节点的距离和路径。