【ダイクストラ法】数学扱いされなかった20分の発想は、なぜ70年も速くなり続けたのか──PC-98の駅すぱあと、カーナビ、そして2025年の突破

ご視聴ありがとうございます。 1956年、アムステルダムのカフェのテラスで、ひとりの若いプログラマが紙も鉛筆も使わずに20分で考えた「いちばん短い道」の探し方。当時は数学扱いされず、3年間どこにも発表されませんでした。 それから70年。答えが出るまでの時間は何けたも縮みましたが、「近い順に確定させる」という骨組みは今も残っています。PC-98の駅すぱあと、答えを全部CD-ROMに焼いた乗換案内、カーナビのAスター、交差点ごとの「メモ」を使う高速化——速くする工夫はどこに積まれたのか。そして、なぜ骨組みは替えられなかったのか。2024年の「最善」の証明と、2025年の突破までを追います。 ■ 関連動画 BASIC回（ダイクストラの「BASIC批判」）:    • 【BASIC】なぜ"素人の言語"が世界最大のソフトウェア帝国を生んだのか   パケット回（ルーターは世界地図を持たない）:    • 【パケットって何？】なぜインターネットは1文字も欠けずに届くのか？【届く保証ゼロ】   ソート60年史:    • 世界最速ソートは飲み会で生まれた？ソート60年史【ゆっくり解説】   ■ 参考文献 ・Oral history interview with Edsger W. Dijkstra, by Philip L. Frana, 2001（Charles Babbage Institute, OH 330） ・Dijkstra, "A note on two problems in connexion with graphs", Numerische Mathematik 1 (1959) 269–271 ・Dijkstra, EWD340 "The Humble Programmer"（1972） ・McQuillan, Richer, Rosen, "An Overview of the New Routing Algorithm for the ARPANET"（1979） ・RFC 1131 "The OSPF Specification"（1989） ・日経xTECH「『駅すぱあと』は続くよどこまでも」／ジョルダン公式note「乗換案内1993」 ・Hart, Nilsson, Raphael（1968）A* search ・NAVITIME JAPAN 技術ブログ「高速な経路探索アルゴリズムの実装と課題」（2019） ・Akiba, Iwata, Kawarabayashi, Kawata, "Pruned Highway Labeling", ALENEX 2014 ・Fredman & Tarjan, "Fibonacci heaps…", JACM 1987 ・Haeupler, Hladík, Rozhoň, Tarjan, Tětek, "Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps", FOCS 2024 ・Duan, Mao, Mao, Shu, Yin, "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths", STOC 2025 ・Castro et al., arXiv 2511.03007（2025年の方法の実装比較） ・Vals AI blog "A Faster Shortest Path Algorithm"（2026-09-20・査読前） ※ 製品（駅すぱあと・乗換案内・各社カーナビ）の内部の計算方式は、動画内では断定していません。 ■ 画像出典 写真: Darklanlan / CC0（Wikimedia Commons「PC-9801 computer set.jpg」） 写真: htomari (Flickr) / CC BY 2.0（Wikimedia Commons「NEC PC-9801 RX Personal Computer.jpg」） 写真: 日本交通公社 / PD（Wikimedia Commons「Train timetable in 1957 (Tokyo - Osaka - Kyūshū area).jpg」） 写真: ThisDoesNotComp / CC BY 4.0（Wikimedia Commons「Sony Data Discman DD-8.jpg」） 写真: Gestumblindi / CC0（Wikimedia Commons「Sony-ebook2.jpg」） 写真: ThisDoesNotComp / CC BY 4.0（Wikimedia Commons「Sony Data Discman DD-85.jpg」） 地図データ: Natural Earth（パブリックドメイン） このチャンネルが面白かったらぜひチャンネル登録お願いします。 https://www.youtube.com/@ゆっくり情報科学?sub... ■ 高評価ボタン近くの「ハイプ」での応援もお願いします！（週3回無料・公開7日以内の動画が対象） ■ 画像について 実機の写真には「実機写真」、当時の資料には「資料」、当チャンネルがデータから作図したものには「再現図」のタグを付けています。 「イメージ」タグの画像は生成AIで作った情景イメージで、実在の機器・画面・人物を再現したものではありません。 数字・年表・図解はAIに描かせず、事実シートからプログラムで作図しています。 ゆっくりしていってね！ ※この動画は【東方project】を基にした二次創作です。 東方Projectの二次創作ガイドライン https://touhou-project.news/guideline/ ※ゆっくり魔理沙、ゆっくり霊夢はきつね様の画像を使用しています。 https://ci-en.net/creator/34363/artic... #ダイクストラ法 #アルゴリズム #最短経路 #情報科学 #ゆっくり解説 #コンピュータサイエンス #ITの歴史 #技術解説 ■ チャプター 0:00 オープニング 2:33 第1章 職業のない仕事 5:25 第2章 全部試せばいい、の罠 8:03 第3章 近い点から確定させる 12:15 第4章 3ページに2問 15:34 第5章 ルーターの中の地図 19:18 第6章 渋谷駅とPC-98 22:57 第7章 道は星に聞く 26:30 第8章 計算しない乗換案内 29:49 第9章 1.5秒と1.7マイクロ秒 33:56 第10章 近い順という壁 38:03 第11章 今朝、私の計算を 43:01 エンディング