戴克斯特拉演算法

戴克斯特拉演算法是一套用來在網路裡尋找「最省路線」的方法：它能從一個起點出發，算出到其他每一個點的最便宜走法，而點與點之間的每一步都帶有一個代價——比如距離、時間或能量。想像一張地鐵路線圖，每兩個相鄰站之間都標著要花多少分鐘。這個演算法不是靠猜，而是像水漫過山谷那樣，耐心地從起點一圈圈向外擴散，算出從你家附近那一站到任意目的地的最快總用時：它每一步總是先去「敲定」當前離起點最近、還沒確定下來的那個站，因此當它第一次把某個站敲定時，就已經確定那是到那裡最快的走法。

讓它如此可靠的訣竅是這樣的：演算法為每一個點都記著一個「目前已知的最低到達代價」，起點記為零，其餘各處先記為「未知」。它反覆挑出尚未敲定、且已知代價最小的那個點，把它標記為最終確定，然後查看它的鄰居：如果經過這個點去到某個鄰居比之前找到的任何走法都更便宜，就把那個更低的代價記下來。正因為它每次都先敲定「目前最便宜」的點，而且各步代價永遠不會是負數，後面任何新發現都不可能再打敗一個已經鎖定的點。演算法結束時，到達目標的最短路徑就能一步步回溯出來。

在機器人路徑規劃裡，這些「點」就是柵格地圖裡的方格，或是機器人可以站立的各個位置所組成的圖中的節點，而「代價」則是在它們之間移動有多困難或多危險。戴克斯特拉演算法能保證給出真正最短、或代價最低的路徑，這是它最大的長處。它的短處是會朝各個方向同等地探索，完全不知道目標在哪邊，因此可能把力氣浪費在遠離目標的地方——而這正是 A* 搜尋演算法透過加入一個「朝哪個方向走」的提示所要解決的問題。