最短路径问题 最短路径问题是图论中的经典问题，旨在寻找图中两个顶点之间路径长度最小的路径。这里的“长度”通常指路径上所有边的权重之和。 问题定义与核心概念 带权图 ：我们首先需要一个图，其中每条边都被赋予一个数值，称为“权重”或“长度”。这种图称为带权图。权重可以表示实际距离、时间、成本等。 路径长度 ：一条路径的长度定义为该路径上所有边的权重之和。 最短路径 ：连接顶点u和顶点v的所有路径中，长度最小的那条路径就是u到v的最短路径。其长度称为u到v的最短距离。 单源最短路径算法：Dijkstra算法 当我们需要找出从一个特定的顶点（称为“源点”）到图中所有其他顶点的最短路径时，这个问题称为单源最短路径问题。最著名的算法是Dijkstra算法。 核心思想 ：采用一种“贪心”策略，按距离源点由近及远的顺序，逐步确定每个顶点的最短路径。 算法前提 ：该算法要求图中所有边的权重均为非负值。 详细步骤 ： a. 初始化 ：创建一个集合 S ，用于存放已经找到最短路径的顶点。初始时， S 只包含源点 s 。为每个顶点v维护两个属性： dist[v] 表示当前从 s 到v的最短距离估计值（初始时， dist[s] 设为0，其他顶点设为无穷大）； prev[v] 记录v在最短路径上的前一个顶点。 b. 迭代过程 ：当 S 未包含所有顶点时，重复以下步骤： i. 选择 ：从不在 S 中的顶点里，选择一个 dist 值最小的顶点 u 。 ii. 收录 ：将顶点 u 加入集合 S ，此时 dist[u] 就是 s 到 u 的最终最短距离。 iii. 松弛 ：检查 u 的所有不在 S 中的邻居顶点 v 。计算 dist[u] + weight(u, v) （即从 s 先到 u ，再从 u 到 v 的距离）。如果这个值小于当前的 dist[v] ，则更新 dist[v] 为这个更小的值，并设置 prev[v] = u 。 简单例子 ：想象一个城市地图，顶点是路口，边是道路，权重是通行时间。Dijkstra算法就像是你从家（源点）出发，总是先探索当前已知的能最快到达的邻近路口，并基于这个路口的信息，更新到达其他更远路口的时间估计。 所有顶点对最短路径算法：Floyd-Warshall算法 当我们需要计算图中任意两个顶点之间的最短路径时，如果对每个顶点都运行一次Dijkstra算法会比较低效（尤其是在边权重可为负时）。Floyd-Warshall算法直接解决了所有顶点对之间的最短路径问题。 核心思想 ：动态规划。它考虑图中顶点的一个子集，并逐步扩大这个子集，允许更多的顶点作为中间顶点。 算法前提 ：可以处理有正权或负权的边，但不能存在权重和为负的环（因为可以在环上无限绕行使得路径长度趋于负无穷）。 详细步骤 ： a. 初始化 ：用一个二维数组 dist 来存储最短距离估计。 dist[i][j] 表示从顶点i到顶点j的当前最短距离。初始时，如果i等于j，则 dist[i][j] = 0 ；如果i和j之间有边，则 dist[i][j] 为边的权重；否则设为无穷大。 b. 迭代过程 ：依次考虑每个顶点k（从1到n）作为潜在的中间顶点。对于每一对顶点(i, j)，检查是否存在一条从i到j的路径，经过顶点k，会比当前已知的路径更短。 更新规则为： dist[i][j] = min( dist[i][j], dist[i][k] + dist[k][j] ) 这意味着：“从i到j的最短路径，要么是不经过k的原始路径，要么是先从i到k，再从k到j的路径之和”。 简单理解 ：想象逐步开放交通中转站。首先，不允许任何中转（直接距离）；然后允许使用第1个城市中转，更新所有城市间的最短路线；接着允许使用第1和2号城市中转，再次更新；以此类推，直到允许使用所有城市作为中转站，此时得到的就是最终的最短路线表。