北京
1956年，阿姆斯特丹。一个年轻程序员陪女朋友逛街，走累了，两人在街边咖啡馆坐下。咖啡端上来，女朋友慢慢喝，他盯着杯子发呆。二十分钟后，他把咖啡杯一推，脑海里已经跑完了一整套算法——没有纸，没有笔，全凭脑子。这个程序员叫艾兹赫尔·戴克斯特拉，那二十分钟里想出来的东西，后来成了GPS导航、网络路由、供应链调度、机器人路径规划的核心。别人喝完咖啡顶多解个乏，他直接给世界解了一道最短路径的题。
最近自由编程营（freeCodeCamp.org）的YouTube频道上线了一个新视频，专门把戴克斯特拉算法从头到尾扒了一遍。主讲人Estafania带着观众先回到那个咖啡馆午后，再一步步把这套算法的内脏摊开来看。看完你会发现，这个在咖啡香里冒出来的想法，比很多花了几百页论文折腾出来的模型都实用。
戴克斯特拉当年给自己设了个限制：不用纸笔。这个看似自虐的要求，反而逼出了算法极其简洁的结构。没有草稿就意味着不能靠反复试错去凑，每个逻辑分支都得在脑子里验证完毕。所以最终诞生的解法，几乎没有冗余步骤，至今都是教科书里最短路径问题的入门首选。这种“脑内预演完整逻辑”的能力，放到今天，大概可以让996的程序员们集体沉默。
视频先从怎么把现实世界的路网变成抽象数据结构讲起。一条条道路、一个个路口，被抽象成图：节点代表地点，边代表道路，边上的权重可能是距离、时间、甚至收费金额。这种建模方式早就不限于地图了，社交网络里的人是节点，好友关系是边；互联网路由器是节点，光纤是边；器官移植分配系统里，捐献者和受者也是节点。把现实问题翻译成图，就等于拿到了算法的入场券。
建好图之后，视频用逐步可视化的方式演示了如何从起点到终点找出最短路径。核心逻辑极其直白：每一步都只看眼前最好的选择。起点周围一圈节点，先挑距离最小的那个，把它标记为“已处理”，然后更新它邻居的距离值，再从未处理的节点里挑最小的，反复循环。这种“贪心”策略，就是贪心算法的典型特征——每步都追求局部最优，但戴克斯特拉证明了，只要边权重非负，局部最优攒起来就是全局最优。
这里有个细节很值得吐槽。很多算法课程讲到贪心策略时，喜欢用找零钱、活动安排当案例，让人误以为贪心就是贪小便宜。但戴克斯特拉算法实际上把“贪”上了一种强约束：它用一个最小堆（min-heap）作为优先队列，保证每次取出的都是当前未处理节点中距离最小的那个。不是闭着眼睛随便贪，而是用数据结构把贪心变成确定性动作。这种设计让时间复杂度直接降到了对数级别，对于动辄百万节点的路网，这就是能不能出结果的差距。
最后，视频把理论扔进Python代码里。用邻接表表示图——一个字典，每个节点对应的值是一个列表，列表里装着邻居和到邻居的距离。然后初始化距离数组，起点的距离设0，其余设无穷大。优先队列里塞进起点，每一次弹出队首，检查它的邻居：如果从当前节点过去比原来记录的更短，就更新距离并把邻居推进队列。等队列空了，距离数组里躺着的就是从起点到任意节点的最短距离。到此还不算完，视频又教了一个回溯函数：从终点开始，沿着每次被更新的“前驱节点”往回走，直到起点，这条路径打印出来，就是导航软件里那条蓝线。
二十二分钟，视频结束。从一杯咖啡的灵感，到图抽象、贪心策略、优先队列优化，再到Python跑通和路径回溯，全部讲得干干净净。推荐给算法面试刷到心态崩了的人：别光背模板，先把这个咖啡馆里的老故事听完，可能比刷十道题更有用。
特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
