迪杰斯特拉算法（Dijkstra算法）

资 源 简 介

迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。 Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时

详 情 说 明

在这段文本中，我们介绍了迪科斯彻算法的工作原理。迪科斯彻算法是一种用于解决赋权有向图或者无向图的单源最短路径问题的算法。该算法通过使用广度优先搜索，最终得到一个最短路径树。它常被用作路由算法或其他图算法的子模块。

具体而言，Dijkstra算法采用了一种贪心的策略。它使用一个数组dis来保存源点到各个顶点的最短距离，并使用一个集合T来保存已经找到了最短路径的顶点。初始时，源点s的路径权重被赋为0，同时其他顶点的路径长度被设为无穷大。初始时，集合T只包含顶点s。

然后，我们从dis数组中选择最小值，这个值对应的顶点就是源点s到该顶点的最短路径。我们将这个顶点加入到集合T中。这样，我们完成了一个顶点的处理。接下来，我们需要检查新加入的顶点是否可以到达其他顶点，并且通过这个顶点到达其他顶点的路径长度是否比源点直接到达的路径长度更短。如果是的话，我们就替换dis中这些顶点的值。

然后，我们再次从dis中找出最小值，重复上述的步骤，直到集合T中包含了图的所有顶点。通过这种方式，我们可以找到源点到图中所有顶点的最短路径。