算法图解 - 狄克斯特拉算法
🏷️ 《算法图解》
若图中的边加了权值，如何找出权值最小的路径? => 狄克斯特拉算法 (Dijkstra's algorithm)
步骤
找出 "最便宜" 的节点。
更新该节点的邻居的开销 (为了计算最终路径，需要保存到达该节点的最小开销时的父节点)。
重复这个过程，直到对图中的每个节点都这么做了。
计算最终路径 (根据保留的父节点生成最终路径)。
术语
权重 (weight)
非加权图 (unwighted graph) => 广度优先搜索
加权图 (weighted graph) => 狄克斯特拉算法
狄克斯特拉算法只适用于有向无环图 (directed acyclic graph，DAG)
负权边
不能将狄克斯特拉算法用于包含负权边的图。
在包含负权边的图中，要找出最短路径，可使用另一种算法 -- 贝尔曼 - 福德算法 (Bellman-Ford algorithm)。