转：一个极简的Dijkstra算法示例

Dijkstra算法是一种用于计算一个起点到其他所有点的最短路径的算法。它是贪心算法的一种，基于贪心策略，用来找单源最短路径问题。该算法常用于路由算法和作为其他图算法的一个子模块。 Dijkstra算法的时间复杂度为O(E + VlogV)。

下面是一个使用 Dijkstra 算法求最短路径的示例：

假设有一张图，有节点 A, B, C, D, E，边的权重如下：

A -> B : 3

A -> C : 5

B -> C : 1

B -> D : 7

C -> D : 2

C -> E : 4

D -> E : 1

要求从节点 A 到节点 E 的最短路径。

首先，我们将所有节点初始化为未确定状态。

A 的距离为 0，其余节点距离为正无穷。

接着，我们选择距离最小的节点进行更新。

选择 A，将其状态设为已确定。

更新 B, C 的距离: B(3), C(5)

接下来选择下一个距离最小的节点进行更新。

选择 B，将其状态设为已确定。

更新 C, D 的距离: C(4), D(9)

以此类推，直到所有节点都被确定，最终得到最短路径 A->B->C->D->E，长度为7

这只是一个简单的示例，在实际应用中，Dijkstra算法通常需要使用优先队列来维护未确定节点的距离，以提高效率。