迪杰斯特拉算法

迪杰斯特拉算法是一套用来在网络里寻找“最省路线”的方法：它能从一个起点出发，算出到其他每一个点的最便宜走法，而点与点之间的每一步都带有一个代价——比如距离、时间或能量。想象一张地铁线路图，每两个相邻站之间都标着要花多少分钟。这个算法不是靠猜，而是像水漫过山谷那样，耐心地从起点一圈圈向外扩散，算出从你家附近那一站到任意目的地的最快总用时：它每一步总是先去“敲定”当前离起点最近、还没确定下来的那个站，因此当它第一次把某个站敲定时，就已经确定那是到那里最快的走法。

让它如此可靠的诀窍是这样的：算法为每一个点都记着一个“目前已知的最低到达代价”，起点记为零，其余各处先记为“未知”。它反复挑出尚未敲定、且已知代价最小的那个点，把它标记为最终确定，然后查看它的邻居：如果经过这个点去到某个邻居比之前找到的任何走法都更便宜，就把那个更低的代价记下来。正因为它每次都先敲定“目前最便宜”的点，而且各步代价永远不会是负数，后面任何新发现都不可能再打败一个已经锁定的点。算法结束时，到达目标的最短路径就能一步步回溯出来。

在机器人路径规划里，这些“点”就是栅格地图里的方格，或是机器人可以站立的各个位置所组成的图中的节点，而“代价”则是在它们之间移动有多困难或多危险。迪杰斯特拉算法能保证给出真正最短、或代价最低的路径，这是它最大的长处。它的短处是会朝各个方向同等地探索，完全不知道目标在哪边，因此可能把力气浪费在远离目标的地方——而这正是 A* 搜索算法通过加入一个“朝哪个方向走”的提示所要解决的问题。