dijkstra算法详细步骤

dijkstra 算法用于查找加权图中从源点到所有其他点的最短路径，步骤如下：初始化顶点集合 v、距离映射 dist 和上一个顶点映射 prev；主循环中选择距离最小的顶点 u，更新相邻顶点的距离和上一个顶点；当 v 中所有顶点已处理时，算法结束。

Dijkstra 算法详细步骤

Dijkstra 算法是一种用于在加权图中查找从源点到所有其他点的最短路径的贪婪算法。其步骤如下：

1. 初始化

• 创建一个包含图中所有顶点的集合 V。
• 创建一个包含起始点到所有其他点的距离的映射 dist，初始值为无穷大，起始点为 0。
• 创建一个包含起始点到所有其他点的上一个顶点的映射 prev，初始值均为 null。

2. 主循环

• 从 V 中选择一个距离最小的顶点 u。
• 对于所有与 u 相邻的顶点 v，计算经过 u 到达 v 的距离 new_dist。
• 如果 new_dist 小于 dist[v]，则更新 dist[v] 和 prev[v]。

3. 停止条件

• 当 V 中的所有顶点都已被处理时，算法结束。

算法示例

考虑以下加权图：

    A(0)
   / \
  /   \
 B(1)  C(2)

登录后复制

其中数字表示权重。

初始化：

• V = {A, B, C}
• dist = {A: 0, B: ∞, C: ∞}
• prev = {A: null, B: null, C: null}

主循环：

1) 第一次迭代：

• u = A
• 对于 B：new_dist = 0 + 1 = 1
• 对于 C：new_dist = 0 + 2 = 2
• 更新 dist[B] = 1 和 prev[B] = A
• 更新 dist[C] = 2 和 prev[C] = A

2) 第二次迭代：

• u = B
• 对于 C：new_dist = 1 + 2 = 3
• new_dist > dist[C] = 2，因此不更新

输出结果：

• dist[B] = 1
• dist[C] = 2
• prev[B] = A
• prev[C] = A

以上就是dijkstra算法详细步骤的详细内容，更多请关注其它相关文章！

Tags： 顶点算法