Dijkstra算法：单源最短路径

"权非负的单源最短路径算法Dijkstra-数据结构最短路径算法" Dijkstra算法是解决图论中一个经典问题——单源最短路径问题的算法，由荷兰计算机科学家艾兹格·迪科斯彻在1956年提出。这个算法适用于寻找带权有向图中从指定源顶点到其他所有顶点的最短路径，前提条件是图的边权重必须为非负值。 在Dijkstra算法中，我们首先将所有顶点分为两个集合：已知最短路径集合S和未知最短路径集合V-S。源顶点v0被放入集合S，其他顶点位于集合V-S。算法的主要过程如下： 1. 初始化：设置源顶点v0的路径长度为0，其他所有顶点的路径长度为无穷大（表示未找到路径），并将源顶点加入集合S。 2. 贪心选择：从集合V-S中选取一个具有当前最短路径长度的顶点w，将其加入集合S。这里的“当前最短路径长度”是指从源顶点v0到该顶点w的路径长度。 3. 更新路径：检查w的所有邻接顶点，如果通过w可以找到更短的路径到达这些邻接顶点，就更新这些顶点的路径长度。 4. 重复步骤2和3，直到集合V-S为空，即所有的顶点都已被加入集合S，此时我们得到了从源顶点v0到所有其他顶点的最短路径。 在Dijkstra算法的实施过程中，可以使用优先队列（如二叉堆）来高效地选取当前路径长度最小的顶点。对于每一步，优先队列会返回当前未处理顶点中路径长度最小的一个。 举个例子，考虑一个从福州大学到东街口的道路图，其中每个边的权重代表了距离。Dijkstra算法会逐步找到从v0（福州大学）到其他所有顶点的最短路径。例如，v0到v2的最短路径是(v0, v2)，长度为10；v0到v3的最短路径是(v0, v4, v3)，长度为50等。 Dijkstra算法在实际应用中非常广泛，例如在网络路由、旅行商问题、图形渲染等领域都有其身影。需要注意的是，如果图中存在负权边，Dijkstra算法将无法正确工作，因为其基于贪心策略，而负权边可能导致更短的路径在后续的迭代中出现。对于带有负权边的最短路径问题，可以考虑使用其他算法，如Bellman-Ford算法。