2.1.2 经典图算法：最短路径、最小生成树、最大流最小割

文档摘要

2.1.2 经典图算法：最短路径、最小生成树、最大流最小割在图算法的浩瀚星图中，最短路径、最小生成树与最大流最小割，从来不是三颗孤立的星辰——它们是同一片拓扑疆域上相互映照的三重镜像：一个关乎时间效率（从A到B最快要走多久），一个关乎结构经济性（如何用最少的边连通所有节点而不成环），一个关乎系统承载力（这张网络的咽喉要道到底能吞吐多少？瓶颈又在哪儿？）。可悲的是，太多教材把它们讲成三段独立的定义+伪代码+复杂度分析，仿佛算法是供人顶礼膜拜的神龛；而现实中的工程师，却总在凌晨三点对着一个超时的Dijkstra调试图灵光乍现：“等等——我建的图里有负权边吗？优先队列用的是还是？堆顶弹出后有没有做lazy deletion？” 今天，我们不谈“是什么”，只拆解“怎么做”。