Dijkstra 演算法（Dijkstra's algorithm）

想像在一張道路地圖的某一點潑水，水會沿著道路流動，速度由每條路的成本決定。水最先抵達最近的城鎮，接著是次近的，向外擴散，且總是接著確定最近的、尚未處理完的城鎮。Dijkstra 演算法正是以這種『先近後遠』的精神算出最低成本路徑，而它是每個連結狀態路由協定內部的引擎。

它從一個來源節點出發，逐步擴大一個『已完成』節點的集合，這些節點從來源算起的真正最低成本已經確定。每個節點有一個暫定距離，來源從 0 開始，其餘所有人從無窮開始。反覆地：挑出暫定距離最小的未完成節點，把它標為已完成（它的距離現在定案），並對它的每個鄰居檢查，看看穿過這個剛完成的節點是否能得到更便宜的路線——若是，就降低那個鄰居的暫定距離（這個步驟稱為鬆弛，relaxation）。當所有節點都完成時，你就有了到每個目的地的最低成本路徑，以及沿途的第一跳，那正是要放進轉送表的東西。

為什麼它行得通：因為演算法總是定案全域上最近的剩餘節點，而成本非負，所以之後的任何發現都不可能勝過你已經定案的路徑。正是這個保證，讓握有同一張完整地圖的各台連結狀態路由器，能各自獨立地跑 Dijkstra，得出一致、無迴圈的路由。OSPF 字面上就把它的計算叫做 SPF（最短路徑優先），那就是 Dijkstra。

一個誠實的提醒：Dijkstra 要求連結成本非負——負成本會破壞『先近後遠』的保證（那是 Bellman-Ford 的領域）。它也需要完整的圖，所以只適合連結狀態路由，不適合距離向量。配上好的優先佇列它跑得很有效率，但拓樸一變路由器仍得重算，這也是頻繁的連結抖動代價昂貴的原因。