算法之狄克斯特拉算法

介绍加权图——提高或降低某些边的权重。

寻路

狄克斯特拉算法包含4个步骤。
(1) 找出“最便宜”的节点，即可在最短时间内到达的节点。
(2) 更新该节点的邻居的开销，其含义将稍后介绍。
(3) 重复这个过程，直到对图中的每个节点都这样做了。
(4) 计算最终路径。

寻路

第一步 ：找出最便宜的节点。你站在起点，不知道该前往节点A还是前往节点B。前往这两个节点都要多长时间呢？前往节点A需要6分钟，而前往节点B需要2分钟。至于前往其他节点，你还不知道需要多长时间。

第二步 ：计算经节点B前往其各个邻居所需的时间。

第三步 ：重复！

权重 （weight）

权重

带权重的图称为加权图 （weighted graph），不带权重的图称为非加权图 （unweighted graph）。

要计算非加权图中的最短路径，可使用广度优先搜索 。要计算加权图中的最短路径，可使用狄克斯特拉算法 。

如果有负权边，就不能使用狄克斯特拉算法。