dijkstra算法方法理论

Dijkstra算法是一种用于寻找图中两点之间最短路径的经典算法，其名字源于荷兰计算机科学家艾兹格·迪克斯特拉（Edsger Dijkstra）。这个算法基于贪心策略，在无权图或加权非负边的有向图中工作得非常好。

以下是Dijkstra算法的基本步骤：
1. **初始化**：将起始节点标记为已访问，并赋予其距离为0；其余所有节点的距离设为无穷大。
2. **选择最小值**：从未访问过的节点中选取当前距离最小的节点（通常称为“源”节点）。
3. **更新邻接节点**：对于选中的节点，检查它的每一个未访问邻居。如果通过该节点到达邻居的距离比邻居当前已知的距离更小，则更新邻居的距离并将其标记为已访问。
4. **重复直到终点**：继续上述过程，直至目标节点被访问或者无法找到更短路径为止。

Dijkstra算法保证返回的结果总是最优的，因为它总是优先考虑未探索的节点中距离最小的一个。由于它每次只处理一个节点，所以效率上不如A*搜索等其他启发式搜索算法，但是对于简单图来说，Dijkstra已经足够高效。