算法图解 - 狄克斯特拉算法

🏷️ 《算法图解》

若图中的边加了权值，如何找出权值最小的路径? => 狄克斯特拉算法 (Dijkstra's algorithm)

步骤

1. 找出 "最便宜" 的节点。

2. 更新该节点的邻居的开销 (为了计算最终路径，需要保存到达该节点的最小开销时的父节点)。

3. 重复这个过程，直到对图中的每个节点都这么做了。

4. 计算最终路径 (根据保留的父节点生成最终路径)。

术语

• 权重 (weight)

• 非加权图 (unwighted graph) => 广度优先搜索

• 加权图 (weighted graph) => 狄克斯特拉算法

• 狄克斯特拉算法只适用于有向无环图 (directed acyclic graph，DAG)

负权边

• 不能将狄克斯特拉算法用于包含负权边的图。

• 在包含负权边的图中，要找出最短路径，可使用另一种算法 -- 贝尔曼 - 福德算法 (Bellman-Ford algorithm)。