再看最後一眼：地圖與動作
在我們開始計算任何東西之前，讓我們最後一次釘牢這個差別，因為它就是這個段落的全部重點。轉送（forwarding）是路由器對單一封包所做的快速、本地動作：讀出目的地、在一張表裡查找、把封包推出正確的介面，全程在奈秒之內。路由（routing）則是那件緩慢、需要思考的工作，它一開始就是要把那張表填好：決定橫越整張網路時，哪條路徑真的最好。前面 IP 那個段落讓你看到了那個動作；這一篇講的是建立那張讓動作正確的地圖。如果轉送與路由之間還覺得模糊，想像一位早已熟門熟路的快遞員（轉送）對上那位畫出道路地圖的都市規劃者（路由）。
上一篇把規劃者的原料交到了我們手上：把網路畫成一張圖（graph）。每台路由器是一個節點，兩台路由器之間的每條鏈路是一條邊，而每條邊都帶著一個數字，叫做它的成本或權重——它也許反映距離、金錢或某條鏈路的壅塞程度，但對演算法而言它只是個拿來相加的數字。這樣一張網路圖讓我們能問一個精確的問題，而不是含糊的問題。不是「哪條路徑感覺不錯？」，而是「在從這台路由器走到那台的所有走法裡，哪一條的邊成本總和最小？」
這個精確的問題有個名字：尋找最低成本路徑。而這裡有個值得大聲講出來的細微之處——最低成本路徑不一定是跳數最少的那條。經過兩條快速、負載輕的鏈路的兩跳路線，很容易就勝過經過單一條緩慢、壅塞鏈路的一跳路線。路由的全部藝術，就活在「明智地選擇成本」這件事裡；一旦成本訂好了，演算法就只是做誠實的算術。
認識網路的兩種方式
路由演算法有兩大家族，而它們之間的差別，其實就在於每台路由器能看到地圖的多少。在鏈路狀態路由（link-state routing）中，每台路由器最終都握有整張網路的完整地圖——每個節點、每條鏈路、每個成本——然後私下自己算出各自的最佳路徑。在距離向量路由（distance-vector routing）中，沒有任何一台路由器看得到整張地圖；每台只認識它的直接鄰居，並信任那些鄰居告訴它關於其餘部分的事，就像問你旁邊的人「從你站的地方到車站還有多遠？」這一篇講鏈路狀態的故事；下一篇講距離向量的故事，那裡有個著名的錯誤等著我們去認識。
一台位於鏈路狀態網路中的路由器，明明在物理上只看得到插在它身上的那些鏈路，它怎麼拿到整張地圖？靠的是一個叫做「泛洪」（flooding）的步驟。每台路由器量出它到自己每個直接相連鄰居的成本，把那一小份清單裝進一則叫做「鏈路狀態通告」的訊息，然後把它泛洪給其他每一台路由器——每台收到新通告的路由器，會把它從自己其餘所有的鏈路再轉送出去，於是消息像謠言一樣傳遍整張網路。一旦每台路由器都聽過其他所有人的通告，每一台就能從這些碎片重組出完整的圖。現在它們全都握著同一張地圖了。
Dijkstra 演算法：貪婪，卻可證明正確
現在每台路由器都有同一張完整的圖了。把它變成一張路由表，是 Dijkstra 演算法的工作，它以 Edsger Dijkstra 為名——他在 1956 年勾勒出這套方法。這個想法美在它的固執。路由器維護兩群節點：那些從源點算起、真正最便宜成本已經塵埃落定、不再更改的；以及那些還在試探中的。它同時為每個節點記著：目前找到的最便宜成本，以及你會從哪個鄰居抵達。然後它重複一個動作直到完成：在所有還在試探中的節點裡，挑出試探成本最小的那一個，把那個成本宣告為最終值，並用它去鬆弛它的鄰居。
「鬆弛」（relax）這個詞的意思只是：檢查一下，經過我們剛剛敲定的那個節點，去抵達它某個鄰居，是否比我們先前所有的辦法都更便宜，如果是，就把較低的成本記下來。這之所以行得通，靠的是演算法核心的那個貪婪洞見：如果整條邊界上最小的試探成本是，比方說，7，那麼 7 就一定是那個節點真正的最終成本，因為通往它的任何其他路徑，都得先經過某個抵達成本至少為 7 的節點——所以絕不可能更便宜。（這仰賴成本非負，而對網路鏈路成本來說它們永遠非負；Dijkstra 在有負邊時並不安全，但沒有任何頭腦清醒的路由器會給一條鏈路指派負成本。）
- 從你自己的路由器，也就是源點，開始。把它的成本設為 0，其餘每個節點的成本設為無窮大（意思是「尚未找到路徑」）。把所有節點標記為試探中。
- 在試探中的節點裡，挑出成本最小的那一個。把那個成本宣告為最終值，並把該節點移入完成集合——它的最便宜路徑現在已永遠確定。
- 鬆弛那個節點的鄰居：對每個鄰居，算出（該節點的最終成本）加上（通往那個鄰居的鏈路成本）。若這勝過鄰居目前的試探成本，就把它降下來，並記住你會經由這個節點抵達。
- 重複「挑選並鬆弛」這個動作，直到每個節點都完成。那些「經由抵達」的指標，現在就描出了通往每個目的地的最低成本路徑，而每條路徑的第一跳，就成為轉送表裡的一列。
一個小小的演練範例
數字能讓這件事變得具體。假設我們的路由器是節點 A，這張圖有五個節點 A、B、C、D、E，鏈路成本如下：A-B 是 2，A-C 是 5，B-C 是 1，B-D 是 4，C-E 是 2，D-E 是 1。我們要找 A 通往每個人的最低成本路徑。看看貪婪的挑選如何一直選出邊界上最小的成本，以及鬆弛 B 通往 C 的那條便宜鏈路，如何悄悄修正了「直連 A-C」當初訂得太高的、通往 C 的成本。
Links: A-B=2 A-C=5 B-C=1 B-D=4 C-E=2 D-E=1 (source = A) step finalize via | tentative costs from A (cost, via) ---- -------- ---- | B C D E 0 A (0) -- | 2,A 5,A inf inf 1 B (2) A | -- 3,B 6,B inf <- C drops 5->3 via B 2 C (3) B | -- -- 6,B 5,C 3 E (5) C | -- -- 6,B -- <- E=3+2 via C beats nothing yet 4 D (6) B | -- -- -- -- Final least-cost paths and FIRST HOP from A: to B : cost 2, path A-B, first hop B to C : cost 3, path A-B-C, first hop B to D : cost 6, path A-B-D, first hop B to E : cost 5, path A-B-C-E, first hop B
看結果的最後一欄：轉送表永遠只存第一跳，而不是整條路徑。要抵達 E，A 不需要記住「先 A 再 C 再 E」；它只需要知道「把它送給 B，並信任 B 把剩下的做完」。這正是路由與轉送之所以如此貼合的深層原因——每台路由器都在同一張公認的地圖上跑 Dijkstra，於是它們各自獨立算出的第一跳，串接成一條一致的端到端路徑，而沒有任何一台路由器需要去指揮整條路線。
從課本走向真實的網際網路
這不只是課堂練習。在真實網路內部，最廣為使用的鏈路狀態協定是 OSPF（Open Shortest Path First，開放最短路徑優先），而它名字裡的那個「最短路徑優先」，就是 Dijkstra 演算法在 OSPF 泛洪所建出的地圖上運行。這個段落的第四篇會把 OSPF 好好打開來看；現在你只要知道：當一家公司或校園網路裡某處的光纖被切斷、或一台新路由器上線時，一台 OSPF 路由器會把消息泛洪出去，每個人重建出同一張更新後的地圖，而每台路由器靜靜地重跑 Dijkstra 來刷新它的表。你剛剛親手描過的理論，幾乎是一行對一行地，就是生產級路由器在做的事。