1、一场“偷懒”引发的革命
想象一下，你是一名20世纪50年代的邮差，每天需要穿越荷兰的城镇，把信件送到千家万户。面对错综复杂的街道和桥梁，如何规划最短路线才能少走冤枉路？这个问题不仅困扰着邮差，也难倒了当时的计算机科学家们——直到一位名叫艾兹格·W·迪科斯彻（Edsger Wybe Dijkstra）的荷兰人，在某个清晨的咖啡时间灵光乍现。
“如果我能让计算机自己‘贪婪’地选择最短的路呢？”
这个简单的想法，最终演化成了计算机科学史上最经典的算法之一：Dijkstra算法。它不仅是导航软件的基石，更深刻影响了物流、通信甚至游戏AI的发展。
1956年，27岁的Dijkstra在阿姆斯特丹的数学中心工作。当时的计算机只能处理简单运算，而“最短路径问题”需要复杂的数学建模。但Dijkstra偏偏是个讨厌公式的人，他坚信：“编程的本质是思考，而不是计算。”（后来他成为结构化编程的先驱，还吐槽过“Go To语句有害”）
一天，他受荷兰政府委托设计一种自动计算交通路线的方法。面对地图上的城市和道路，他没有用传统的数学推导，而是另辟蹊径：让计算机模拟人类的选择过程。他设想，如果从起点出发，每一步都选当前能看到的最短路径，最终就能“滚雪球”般逼近全局最优解。
这个算法仅用20分钟就被设计出来，甚至没有写论文——直到3年后，他才在一篇3页的短文中正式发表。而今天，这个“咖啡杯边的灵感”每天被数十亿人使用：从谷歌地图的路线规划，到王者荣耀中英雄的自动寻路，背后都有它的影子。
算法核心：像“贪吃蛇”一样吃掉最短路径
Dijkstra算法的核心思想可以用一句话概括：贪婪地扩展已知最短路径，直到吃掉终点。听起来像一条聪明的贪吃蛇？没错！我们用一个现实场景来拆解它的步骤：
场景：你站在北京中关村（起点），要去天安门（终点），地铁、公交和步行的时间不同。如何找到耗时最短的路线？
第一步：给每个路口贴上“时间标签”
初始化一张表格，记录从起点到每个路口的已知最短时间。初始时，所有路口标记为“无穷大”，只有起点标记为0。
准备一个“待探索列表”，先放入起点。
路口
中关村
西直门
天安门
...
最短时间
0
∞
∞
...
第二步：戴上“时间望远镜”，选当前能看到的最短路径
从“待探索列表”中选出当前时间最短的路口（比如西直门需要20分钟，五道口需要15分钟，则优先探索五道口）。
为什么贪婪？ 因为一旦确定某个路口的最短时间，后续路径的计算可以基于这个结果，无需回头。
第三步：更新邻居的“时间标签”
假设从五道口（当前时间15分钟）出发，发现到西直门的新路线只需15+10=25分钟，而西直门原标记是∞。于是更新西直门的时间为25，并把它加入待探索列表。
这个过程称为松弛（Relaxation）——就像松开紧绷的皮筋，找到更优的路径。
更新后：
路口
中关村
西直门
五道口
天安门
...
最短时间
0
25
15
∞
...
第四步：重复直到“吃掉”终点
不断从待探索列表中选择最短时间的路口，更新邻居，直到终点被选中。此时表格中的值即为最短时间。
代码比喻：一个不断缩小的“候选池”
实际代码通常用优先队列（Priority Queue）实现“待探索列表”，确保每次取出的都是当前最短路径的节点。整个过程像剥洋葱一样层层推进，直到终点暴露在最内层。
为什么Dijkstra算法不能处理“堵车倒贴钱”？
Dijkstra算法有一个著名限制：边权（即时间/距离）不能为负数。比如，如果某条路因为堵车反而能“倒贴时间”，算法可能陷入死循环。
原因：算法假设“一旦确定最短路径就永不更新”，但负权边可能让已确定的路口出现更短路径。就像你刚确认五道口需要15分钟，突然发现一条“时间隧道”能让你瞬间抵达，导致之前的计算结果全部作废。
（解决负权问题需要另一个算法：Bellman-Ford，那是另一个故事了。）
算法的浪漫在于解决真实世界的困惑。Dijkstra算法诞生近70年，依然是计算机教材中最常被提及的经典。它的美在于用极简的规则解决复杂问题——就像Dijkstra本人所说：“简单是可靠的先决条件。”
今天，当你在手机地图上点击“开始导航”时，不妨想象那位荷兰极客在咖啡杯边的灵光一闪。人类对“最短路径”的追求从未停止，而算法正是我们探索世界的指南针。