dijkstra

dijkstra 算法总结

总结

dijkstra 算法核心只有三部操作：

1. 找到未被访问节点中离原点距离最近的节点
2. 标记该节点为已访问
3. 更新该节点的邻居节点到原点的距离

数据包含

• 节点列表 List nodes
• 边列表 List edges
• 距离数组 int[] distances
• 访问数组 boolean[] visited

初始化： 原点到原点的距离设置为0，其他节点到原点的距离设置为无穷大 （因为是算最小值）。
从原点开始，遍历所有邻居节点，当前节点记作cur，则有：

• 当前节点到原点的最近距离 distances[cur]
• 当前节点到邻居节点的距离 edge.weight
• 邻居节点到原点的距离 distances[neighbor]

比较 distances[cur] + edge.weight 与 distances[neighbor] 的大小，如果distances[cur] + edge.weight 更小，说明 neighbor 到原点的距离有更短路径。

则执行具体步骤为：

• 比较 distances[cur] + edge.weight 与 distances[neighbor] 的大小
• （如果有更短路径）更新邻居节点到原点的最小距离 distances[neighbor] = distances[cur] + edge.weight
• 重复以上步骤循环遍历其他邻居节点
• 所有邻居节点都被处理之后，设置当前节点已经被访问 visited[cur] = true
• 更新当前节点 cur 为 未被访问过的节点中离原点距离最小的节点 visited[cur]=false && min(distances[i])
• 重复以上步骤

最终 distances[i] 中记录的就是所有节点离原点的最小距离。

注意：

• 节点之间的距离不能为负数（会影响已经计算过的节点到原点的距离的最小值）
• 如果节点对原点不可达，那么距离永远是初始化的值无穷大