エドガー・ダイクストラ：Google Maps の最短経路を発明したオランダ人

1. 身近な「Google Maps の経路検索」を逆算する

Google Maps の徒歩・電車・車の経路検索、カーナビ、ネットワークルーティング、ゲーム NPC の移動、すべて 「ダイクストラ法」(最短経路アルゴリズム) の応用。1956 年、20 分のコーヒーブレイクで考えたという伝説。

2. 100 文字でわかる

3. 500 文字でわかる

1930 年オランダ・ロッテルダム生まれ、ライデン大学博士。1956 年、当時 26 歳の彼が「ロッテルダムからフローニンゲンまで最短経路は何か」を考え、20 分のコーヒーブレイクで「ダイクストラ法」を発明 (本人談、紙とペンで考えた)。これが現代の Google Maps・ネットワークルーティングの基本アルゴリズム。1968 年、伝説の論文「Go To Statement Considered Harmful (Go To 文は有害である)」を発表、当時の主流 (アセンブリ・FORTRAN の goto 多用) を批判、構造化プログラミング を提唱。これが現代の if / for / while・関数呼び出し 中心の書き方を確立。1972 年チューリング賞。「プログラミングは芸術」「「コード行数の生産性」測定はアプロン (台所掃除エプロン) で重さを測るのと同じく愚か」など、CS 界で愛される警句を多数。極めて頑固で批判的な性格、生涯を通じて多くの「有害論」を発表。2002 年没**。

4. もっと詳しく

ダイクストラ法の発明 (1956)

1956 年、コーヒーブレイクで「ロッテルダムからフローニンゲンまで最短経路は?」を考え、紙とペンで 20 分でアルゴリズムを完成。「最短経路の集合を徐々に拡大する」という発想で、グラフ理論の歴史的進歩。1959 年論文発表。現代の最短経路問題の標準解として、Google Maps・ネットワークルーティング (OSPF)・ゲーム AI 等で日常的に使われる。

Go To 文有害論 (1968)

1968 年、Communications of the ACM に「Go To Statement Considered Harmful」発表。当時のプログラミングは Goto 文 (任意の場所にジャンプ) が多用されており、コードの読解性・正しさが酷かった。ダイクストラは 「Goto を排除し、構造化されたブロック (if / while / for) で書こう」と主張。これが現代の構造化プログラミング → オブジェクト指向の起点。

プログラム正当性証明

「プログラムが正しいことを数学的に証明する」研究を生涯追求。Hoare 論理・Predicate Transformer Calculus 等の理論を確立、形式手法の基礎。

辛口エッセイ (EWD シリーズ)

自筆原稿シリーズ「EWD」(Edsger Wybe Dijkstra)、生涯 1300 通以上。辛辣な批判で多くの著名学者を「有害」「無能」と罵倒、しかし内容の鋭さで尊敬された。「コンピュータ科学はコンピュータには関係ない、天文学が望遠鏡に関係ないのと同じ**」など、警句が多い。

5. 現代への影響

• 最短経路アルゴリズム: Google Maps・GPS・ネットワーク・ゲーム
• 構造化プログラミング: 全現代言語の書き方
• 形式手法: 安全クリティカルなソフトウェア (航空・医療)
• 並行処理: ダイニング哲学者問題 (彼の発明) は並行プログラミングの定番教材
• コンピュータ科学教育: アルゴリズム・データ構造の教科書

6. もっと知りたい人へ

• Wikipedia (日本語): エドガー・ダイクストラ
• EWD アーカイブ: テキサス大学に保管、無料公開
• 書籍「A Discipline of Programming」(1976): 形式手法の名著

7. 次の話

EP.59 では ニール・コブリッツ + ヴィクター・ミラー を扱います。SSL/TLS の基盤 楕円曲線暗号を発明した数学者 2 人。