扫码获取 VIP 码
添加管理员微信获取 VIP 码
最短路径问题是图论领域最经典、也是软考数据结构与算法部分出题频率最高的知识点之一。讨论算法之前，须先厘清它所依赖的数学对象。所谓图，按教材的标准术语，是一个由顶点集合和边集合构成的二元组，记作 G=(V,E)，其中 V 是顶点集合，E 是边集合。当每条边都被赋予一个数值时，这个数值称为该边的权值，此时图称为带权图。最短路径问题的任务，就是在这样一个带权图中，从某个指定源点出发，找到它到其余各顶点之间权值之和最小的一条路径，这条路径上的权值总和就是最短路径长度。
这里须强调一个易被忽视的细节：最短路径中的"最短"，指路径上所有边权值累加的总和最小，而非经过的边数最少。仅在无权图或所有边权相等时，边数最少与权值总和最小才会重合，这也是无权图中广度优先遍历能直接求最短路径的原因。一旦边权各不相同，边数最少的路未必权值最小，广度优先搜索便不再适用，必须引入专门算法。
根据源点与目标点的数量关系，最短路径问题又可细分为几类。单源最短路径要求计算从一个指定源点到其余所有顶点的最短路径；多源最短路径则一次性计算任意两顶点之间的最短路径；此外还有特定点对之间的最短路径。Dijkstra 解决的是单源最短路径，也是软考中考得最密集的一类。
Dijkstra 算法由荷兰计算机科学家艾兹赫尔·戴克斯特拉于一九五六年提出，是求解单源最短路径最著名的算法，其标准应用前提是图中所有边的权值均为非负。教材中对该算法的描述通常概括为：从源点出发，采用贪心策略，每次从未确定最短路径的顶点集合中选出当前距离源点最近者，纳入已确定集合，并借助这个新确定的顶点对其邻接顶点的距离做松弛更新，如此反复，直至所有顶点的最短路径都被确定。
理解这个定义的关键，在于抓住"贪心策略"和"松弛操作"两个核心概念。贪心策略指算法在每一步做出的局部最优选择，即每次总是挑选当前看来距离源点最近的顶点，而不会回溯或推翻之前的选择。松弛操作则是逐步修正距离估计值的基本动作，它回答的问题是：若经由某个中间顶点中转，能否让当前顶点到源点的距离变得更短，若能，就更新这个距离。整个 Dijkstra 算法本质上就是贪心选择与松弛操作交替进行的过程。
在软考的命题体系中，Dijkstra 很少被孤立考查，它往往与算法设计策略的分类捆绑出现。命题人最常问的一句话是：某个算法采用了哪种算法设计策略。因此，考生须对分治法、动态规划、贪心法、回溯法这四种基本策略有清晰的边界认知。
分治法的核心是把大问题递归分解为结构相同、规模较小的子问题，分别求解后再合并，归并排序与快速排序是典型代表。动态规划依赖最优子结构和重叠子问题性质，通过保存子问题的解避免重复计算，最长公共子序列与矩阵链相乘是典型代表。贪心法在每一步都做出当前看来最优的选择，不回溯、不整体规划，哈夫曼编码与最小生成树的 Prim、Kruskal 算法是典型代表。回溯法以深度优先方式系统地搜索解空间，发现当前路径不可能得到解时及时退回，八皇后问题是最典型代表。
Dijkstra 算法之所以被归入贪心法，正因为它在每一步都从尚未确定的顶点中挑出距离源点最近者，这种"永远走当前最近一步"的选择方式，恰是贪心策略的标志性特征，也是软考选择题的高频得分点。
很多人背下了"Dijkstra 是贪心算法"的结论，却不明白为何这种只顾眼前的策略能保证全局最优。要回答这个问题，须回到贪心算法的正确性证明框架：一个贪心策略要成立，通常需问题满足贪心选择性质和最优子结构两个条件，其中贪心选择性质指通过局部最优选择能得到全局最优解。
Dijkstra 满足贪心选择性质的根源，在于所有边权值均为非负这一前提。假设已有一批顶点的最短路径被确定，算法每次从剩余顶点中选出距离源点最近者 v。为何可断言 v 的最短路径此刻已确定、不会再更新？原因在于：从源点到 v 的任何路径，最后一步必然经过 v 的某个前驱顶点 u；u 要么已确定，要么未确定。若 u 尚未确定，根据选择规则，u 到源点的当前距离一定不小于 v 的当前距离，再叠加从 u 到 v 的非负边权，这条经由 u 的路径长度必然不小于 v 的当前距离。由于所有边权都非负，任何未确定顶点的中转都不可能把 v 的距离改得更小，于是 v 的当前距离就是它的最终最短路径长度。正是非负权这个条件把"局部最近"锁定为"全局最短"，这也是负权边一旦出现、贪心正确性根基就会崩塌的原因。
松弛操作是 Dijkstra 乃至整个最短路径算法家族共用的核心机制。它的形式化描述极其简洁：设 dist[u] 表示源点到顶点 u 的当前最短距离估计值，w(u,v) 表示边 u 到 v 的权值，对边 u 到 v 执行松弛操作，就是判断 dist[u] + w(u,v) 是否小于 dist[v]，若成立则令 dist[v] 更新为 dist[u] + w(u,v)。这个判断式是理解一切最短路径算法的钥匙。
从语义上看，松弛操作做的事情非常朴素：它不断试探"绕道走会不会更近"。顶点 v 原本记录着自己到源点的最短距离，但这记录未必是最终答案，因为可能存在一条经顶点 u 中转的路径让距离更短。松弛操作就是逐个拿邻接顶点试探，一旦发现经由 u 中转更近，就立刻修正 v 的距离估计值。算法反复试探，直到没有任何边能再让距离变小，所有顶点记录的距离便收敛为真正的最短路径。
值得强调的是，松弛操作与"记录前驱"往往同步进行。为了让算法结束后能还原出最短路径本身而不仅是长度，通常还为每个顶点维护一个前驱指针。每当 dist[v] 因经由 u 中转被更新时，就把 v 的前驱设为 u。算法结束时从目标顶点沿前驱指针回溯到源点，得到的那条路径就是实际最短路径。考试虽多以求解长度为主，但前驱机制体现的是"长度"与"路径"两个概念的一体两面，有助于完整理解算法。
为把抽象描述落到具体操作上，这里把 Dijkstra 的标准执行流程拆解为清晰步骤。第一步，初始化：将源点到自身的距离 dist[s] 置零，源点到其余顶点的距离初始化为无穷大，同时把所有顶点标记为未确定。第二步，贪心选择：在尚未确定的顶点中，选出 dist 值最小者 u，标记为已确定。第三步，松弛更新：遍历 u 的所有邻接顶点 v，对每条边执行松弛，若 dist[u] 加边权小于 dist[v]，就更新 dist[v] 并记录 v 的前驱为 u。第四步，循环判断：重复第二、三步，直到所有顶点确定，算法终止。
以源点到自身的距离为零、其余为无穷大作为起点，是算法能正常启动的关键。第一次贪心选择必然选中源点自身，随后源点把所有邻接顶点的距离从无穷大修正为相应边的权值。第二次贪心选择则在这些被修正的邻接顶点中选出最近者，再借它向外扩散。可以直观理解为，算法以源点为中心，像水波一样一圈圈向外确定最短路径，直到覆盖全部顶点。这种逐步扩张的过程与无权图中的广度优先搜索相似，区别只在无权图按边数扩张，带权图按权值扩张。
Dijkstra 的时间复杂度与实现方式密切相关，也是命题人偶尔设问之处。朴素实现需执行 V 次贪心选择，每次都要在剩余顶点中扫描找最小者，代价为 O(V)，故选择环节总代价为 O(V²)；松弛更新遍历每条边一次，代价为 O(E)。综合起来朴素实现的整体时间复杂度为 O(V²)，在稠密图上这种实现合适，因为此时 E 的量级接近 V²。
当图较稀疏时，可用优先队列优化贪心选择的效率。将未确定顶点按 dist 值组织进二叉堆，每次取堆顶即为距离最小顶点，取堆顶与调整堆的代价为 O(logV)，每条边最多触发一次松弛并伴随一次堆调整，代价同为 O(logV)，于是总复杂度降为 O((V+E)logV)。若采用斐波那契堆，可进一步优化到 O(E+VlogV)。这些结论虽不要求手写推导，但理解"朴素 O(V²)、堆优化 O((V+E)logV)"这一对关键结论，足以应对绝大多数选择题。
Dijkstra 解决的是单源最短路径，若题目要求任意两点之间的最短路径，则常考 Floyd 算法。Floyd 属于动态规划，以一个递推关系为核心：用顶点编号作为中间顶点的上界，逐步放宽"允许经过哪些顶点中转"的限制。记 d[k][i][j] 为从 i 到 j 只允许经过编号不超过 k 的顶点中转时的最短距离，则 d[k][i][j] 要么不经过顶点 k，要么经过，于是等于 d[k-1][i][j] 与 d[k-1][i][k] 加 d[k-1][k][j] 中的较小值。这一递推式经三重循环即可求解，时间复杂度为 O(V³)，空间上还可通过滚动优化把三维压成一维。
Floyd 与 Dijkstra 在策略上的对比，恰好构成"动态规划与贪心"的鲜活对照，也是命题人乐于设计的辨析点。Dijkstra 每一步锁定一个顶点的最短路径、不再回头；Floyd 则通过逐步扩充可中转的顶点集合，让所有点对的距离共同演化收敛。解题时要根据问题问的是单源还是多源来选用。
当图中存在负权边时，Dijkstra 不再适用，单源最短路径需交给 Bellman-Ford 算法。Bellman-Ford 的核心是对所有边反复执行松弛操作，共 V 减一轮，每轮完整遍历全部边，时间复杂度为 O(VE)。其正确性依据是：一条最短路径最多包含 V 减一条边，因此经 V 减一轮松弛，所有顶点的最短路径必然收敛。它还能检测负权回路：若 V 减一轮结束后仍有边可被进一步松弛，则说明图中存在负权回路，最短路径无意义。
在软考中，Bellman-Ford 常以网络路由协议的形式而非数据结构题被考查。距离向量路由协议，典型代表是 RIP，底层采用的正是 Bellman-Ford 这类分布式松弛思想：每台路由器周期性地把距离向量通告给邻居，邻居据此更新转发表，本质上就是全网范围内不断进行的松弛操作。理解这一点，能把数据结构与网络工程的知识串联起来。