《长安的荔枝》中隐藏的“算法思维”

《长安的荔枝》这本书一经出版，引来了广大读者的一致好评。主人公李善德，“被迫”接受了这个不可能完成的任务，从岭南运送荔枝到长安（荔枝“一日色变，两日香变，三日味变”）。这是一场与时间的赛跑，同时也是李善德同命运的对抗，毫无退路可言，为了家人，更是为了自己，李善德决心放手一搏：“就算失败，他也想知道，自己倒在距离终点多远的地方。

然而历经坎坷，经过千回百转，李善德最终完成了这个看似不可能完成的任务，除了“外部因素”的影响外，有一点也十分重要，就是李善德这个人有脑子，很能算，他运用自己的“算法思维”拆解问题、优化路径、权衡资源，最终创造了跨越五千余里，从岭南运送新鲜荔枝的奇迹。

在整个故事中，可以用“算法”来分析解释的有很多方面。例如问题分解与分治策略，即在算法设计过程中常常引入分而治之的策略，这样的算法叫作“分治算法”，其本质就是将大规模的原问题分解为若干规模较小的与原问题形式相同的子问题，分而治之。在面对“荔枝保鲜+长途运输”这一复杂难题时，若不分解，直接处理会因问题过于庞大复杂而无从下手。将问题拆解为“荔枝选品、路线规划、保鲜技术”三个核心模块，每个模块可视为一个相对独立的子问题（当然还有其他一些问题）。这种分解方式如同将拼图按颜色、图案分成不同区域，先分别处理再整合。

再比如充分运用了动态规划思想。将整个运输距离划分为多个驿站之间的区间，每个区间可看作一个子问题。同时独立规划（因为每个驿站的情况也真是天差地别），即分别规划每个区间内荔枝的保鲜措施，如在驿站更换冷藏容器、补充冰块等，这些子问题相互独立又相互关联。状态转移，即在每个区间内，根据该区间的运输时间、环境温度等因素，确定相应的方案，这就如同动态规划中的状态转移过程，当前区间的方案会影响下一个区间的初始状态。最优解合并，最终将各个区间的方案整合起来，形成一个完整的驿站接力方案，实现了“在荔枝保鲜天数最大化的同时，选择最优驿站路线”，体现了动态规划将子问题最优解合并为原问题最优解的思想。

同时在测试过程不断优化与迭代，将三个核心模块看作一个整体，选择一个最优解，从而完成了这件基本上无法完成的事情。如果将整个过程化零为整，那就是“最短路径”，即在荔枝保鲜的同时用最短的时间将荔枝送到长安。

最短路径算法，包括 Dijkstra 算法、Floyd 算法、Bellman-Ford 算法和 SPFA 算法。由于篇幅所限，仅介绍一下 Dijkstra 算法。

Dijkstra 算法

给定有向带权图 G=(V,Ｅ)，其中每条边的权值都是非负实数。此外，给定集合 V 中的一个节点，称之为“源点”。求解从源点到其他各个节点的最短路径长度，路径长度指路径上各边的权值之和。如何求从源点到其他各个节点的最短路径长度呢？

Dijkstra 算法是用于解决单源最短路径问题的贪心算法，它首先求出长度最短的一条路径，再参照该最短路径求出长度次短的一条路径，直到求出从源点到其他各个节点的最短路径。

Dijkstra 算法的基本思想：假设有源点 u，节点集合 V 被划分为两部分，即集合 S 和集合 V−S。初始时，在集合 S 中仅包含源点 u，集合 S 中从节点到源点的最短路径已确定，集合 V−S 中从节点到源点的最短路径待定。从源点出发只经过集合 S 中的节点到达集合 V−S 中的节点的路径被称为“特殊路径”，用 dist[]数组记录从源点到每个节点的最短特殊路径长度。

Dijkstra 算法采用的贪心策略是选择最短的特殊路径，将其连接的集合 V−S 中的节点加入集合 S，同时更新 dist[]数组。一旦集合 S 包含所有节点，dist[]数组记录的就是从源点到所有其他节点的最短路径长度。 

01

算法步骤

（1）数据结构。用邻接矩阵 G[][]存储地图，用一维数组 dist[i]记录从源点到节点 i 的最短路径长度，用一维数组 p[i]记录最短路径上节点 i 的前驱。 

（2）初始化。令集合 S={u}，对于集合 V−S 中的所有节点 i，都初始化 dist[i]=G[u][i]，若从源点 u 到节点 i 有边相连，则初始化 p[i]=u，否则 p[i]= −1。

（3）找最小。在集合 V−S 中查找 dist[]数组中最小的节点 t，节点 t 是集合 V−S 中距离源点 u 最近的节点。 

（4）加入集合 S。将节点 t 加入集合 S，同时更新集合 V−S。 

（5）判结束。若集合 V−S 为空，则算法结束，否则转向第 6 步。 

（6）借东风。在第 3 步中已经找到了从源点到节点 t 的最短路径，对于集合 V−S 中节点 t 的所有邻接点 j，都可以借助节点 t 走捷径。若 dist[j]>dist[t]+G[t][j]，则 dist[j]=dist[t]+G[t][j]，记录节点 j 的前驱为节点 t，有 p[j]=t，转向第 3 步。 

由此可以求得从源点 u 到图 G 中其他各个节点的最短路径及其长度，也可以通过 p[]数组逆向找到最短路径上的节点。 

02

完美图解

有一个景点地图，如下图所示，求从节点 1 出发到其他各个节点的最短路径。 

（1）数据结构。用邻接矩阵存储地图，若从节点 i 到节点 j 有边，则 G[i][j]等于<i,j>的权值，否则 G[i][j]=∞（无穷大）。

（2）初始化。令集合 S={1}，集合 V−S={2,3,4,5}，对于集合 V−S 中的所有节点 x，都初始化最短距离数组 dist[i]=G[1][i]，dist[u]=0。若从源点 1 到节点 i 有边相连，则初始化前驱数组 p[i]=1，否则 p[i]=−1。

（3）找最小。在集合 V−S={2,3,4,5}中找到 dist[]数组的最小值 2，对应的节点 t=2。

（4）加入集合 S。将节点 2 加入集合 S={1,2}，更新集合 V−S={3,4,5}。

（5）借东风。刚刚已经找到了从源点到节点 t=2 的最短路径，对于集合 V−S 中节点 t 的所有邻接点 j，都可以借助节点 t 走捷径。节点 2 的邻接点是节点 3 和节点 4。首先看节点 3 能否借助节点 2 走捷径：dist[2]+G[2][3]=2+2=4，而当前 dist[3]=5>4，因此可以走捷径，即 2-3。更新 dist[3]=4，记录节点 3 的前驱为节点 2，即 p[3]=2。再看节点 4 能否借助节点 2 走捷径：dist[2]+G[2][4]=2+6=8，而当前 dist[4]=∞>8，因此可以走捷径，即 2-4，更新 dist[4]=8，记录节点 4 的前驱为节点 2，即 p[4]=2。

（6）找最小。在集合 V−S={3,4,5}中找到 dist[]数组的最小值 4，对应的节点 t=3。

（7）加入集合 S。将节点 3 加入集合 S={1,2,3}，更新集合 V−S={4,5}。

（8）借东风。刚刚已经找到了从源点到节点 t=3 的最短路径，对于集合 V−S 中节点 t 的所有邻接点 j，都可以借助节点 t 走捷径。节点 3 的邻接点是节点 4 和节点 5。首先看节点 4 能否借助节点 3 走捷径：dist[3]+G[3][4]=4+7=11，而当前 dist[4]=8<11，比当前路径还长，不更新。再看节点 5 能否借助节点 3 走捷径：dist[3]+G[3][5]=4+1=5，而当前 dist[5]=∞>5，可以走捷径，即 3-5，更新 dist[5]=5，记录节点 5 的前驱为节点 3，即 p[5]=3。

（9）找最小。在集合 V−S={4,5}中找到 dist[]数组的最小值 5，对应的节点 t=5。

（10）加入集合 S。将节点 5 加入集合 S={1,2,3,5}，更新集合 V−S={4}。

（11）借东风。刚刚已经找到了从源点到节点 t=5 的最短路径，对于集合 V−S 中节点 t 的所有邻接点 j，都可以借助节点 t 走捷径。节点 5 没有邻接点，不更新。 

（12）找最小。在集合 V−S={4}中找到 dist[]数组的最小值 8，对应的节点 t=4。

（13）加入集合 S。将节点 4 加入集合 S={1,2,3,5,4}，集合 V−S={}，算法结束。

03

算法实现

想一想：可以通过前驱数组 p[]逆向找到最短路径上的节点，如下图所示。

例如，p[5]=3，即节点 5 的前驱是节点 3；p[3]=2，即节点 3 的前驱是节点 2；p[2]=1，即节点 2 的前驱是节点 1；p[1]= −1，节点 1 没有前驱，则从源点 1 到节点 5 的最短路径为 1-2-3-5。

04

算法分析

时间复杂度：在 Dijkstra 算法中共有 4 个 for 语句，第 1 个 for 语句的执行次数为 n；在第 2 个 for 语句里面嵌套了两个 for 语句。这两个 for 语句的执行次数为 n²，算法的时间复杂度为 O(n²)。空间复杂度：辅助空间包含 flag[]数组及 i、j、t 和 temp 等变量，空间复杂度为 O(n)。 

05

算法优化

（1）优先队列优化。第 3 个 for 语句是在集合 V-S 中查找距离源点 u 最近的节点 t，若用穷举算法来查找，则需要 O(n)时间，进行 n 次查找的总时间复杂度为 O(n²)。 若用优先队列求解，则查找一个最邻近点需要 O(logn)时间，进行 n 次查找的总时间复杂度为 O(nlogn)。 

（2）数据结构优化。第 4 个 for 语句进行了松弛操作，若用邻接矩阵存储图，则访问一个节点的所有邻接点需要执行 n 次，总时间复杂度为 O(n²)。若用邻接表存储图，则访问一个节点的所有邻接点的执行次数为该节点的出度，所有节点的出度之和为 m（边数），总时间复杂度为 O(m)。对于稀疏图，O(m)要比 O(n²)小。

以上内容摘自《算法训练营（提高篇）》，更多关于算法内容见“算法训练营三部曲”。

作者简介

本系列作者陈小玉，副教授，ACM 教练、信息学奥赛教练，拥有丰富的教学经验和深厚的学术造诣，长期从事算法教学和研究工作，培养了大批优秀的算法人才，并出版了多部算法相关的著作。在编写过程中，陈小玉老师充分发挥自己的专业优势，通过大量的实际案例，将复杂的算法知识以通俗易懂的方式呈现给读者。本书配套源码、PPT、视频，提供随时答疑服务。

读者对象

适用于广大算法学习爱好者，包括计算机专业的学生、在职的技术人员以及正在准备求职的求职者等。对于计算机专业的学生来说，本书可以作为教材的补充，帮助他们更好地理解和掌握课堂所学的知识；对于在职的技术人员来说，本书可以帮助他们提升自己的算法能力，适应不断变化的技术需求；对于正在准备求职的求职者来说，本书可以帮助他们掌握算法知识，增加自己的求职竞争力。