1972 Edsger Dijkstra —— 「GOTO 有害」的宣言與最短路徑的算法#

「一位荷蘭程式設計師在 1968 年寫了一封兩頁半的信，整個產業 為之動搖。憑什麼一封信可以當成圖靈獎級的證據？」

案件檔案#

前因#

1960 年代末「軟體危機」爆發：專案延期、錯誤叢生、成本失控。 Brooks 後來稱之「沒有銀彈」（1999 案）。疑點：為什麼程式會 大到沒有人能懂？ 嫌疑人之一：GOTO 指令讓控制流像纏死的毛線球。

線索與推理#

案一：最短路徑（1956/1959）#

問題：荷蘭鐵路網任兩城最短路線。Dijkstra 手持鉛筆 20 分鐘 想出貪心演算法：

1. 起點距離 0，其餘 ∞
2. 取未定點中距離最小者 u，標記為確定
3. 鬆弛 u 的每個鄰居：dist[v] = min(dist[v], dist[u] + w(u,v))
4. 重複 2–3

時間複雜度：O(V²)（陣列版）→ 二元堆積 O(E log V)
正確性不變式：每次標記 u 時，dist[u] 已是全域最短
（因為任何繞過其他未定點的路徑只會更長 —— 邊權非負是關鍵前提！）

證明要點：貪心選擇性質成立的前提是 \(w(u,v) \ge 0\)； 負邊權即失效，需改用 Bellman–Ford。這是「理論前提決定演算法 適用範圍」的教科書案例。

案二：信號量與併發（1965）#

T.H.E. 分時系統中，多個行程搶資源如何不撞車？Dijkstra 發明 信號量（semaphore）——一個原子操作計數器：

P(s): while s==0 wait; s--     （取得）
V(s): s++                      （釋放）

以 P/V 兩個原語操作表達互斥與同步，成為 OS 理論基石 （1983 UNIX 案、1992 Lampson 案均在其延長線上）。 他隨後提出哲學家進餐問題，作為死結（deadlock）的標準試金石。

案三：GOTO 有害論（1968）#

《Go To Statement Considered Harmful》：程式的正確性推理需要 控制流與文字順序對應。GOTO 使「靜態文字」與「動態執行」 脫鉤，歸納推理失效。解方：序列、選擇、循環三種結構——

  { P } S { Q }   的 Hoare 式推理只在結構化控制下可組合
  seq：{P}A{R} 且 {R}B{Q} ⟹ {P} A;B {Q}

理論評析#

Dijkstra 的核心哲學：程式不是寫給機器跑的，是寫給人讀的； 正確性應由構造獲得，而非事後測試。 這條線直通 Hoare 邏輯、 模型檢查（2007 案）與 Pnueli 時態邏輯（1996 案）。

後果#

• 「structured programming」成為所有主流語言的預設形態。
• 他的手寫備忘錄 EWD 系列（數百篇）是計算機科學最優美的 思想文獻。名言：「程式測試只能證明錯誤存在，不能證明錯誤不存在。」

關聯案件#

→ 1980-C.A.R.-Hoare與程式語言理論及CSP、1996-Amir-Pnueli與時態邏輯、1983-Ritchie-Thompson與UNIX作業系統