1. 迪杰斯特拉算法从生活场景到算法思想想象一下你刚搬到一个新的城市周末想去市中心最大的购物中心。打开手机地图你会发现有很多条路可以走有的路红绿灯多有的路距离远但车少。你肯定想找一条“总耗时最短”的路线。这个“找最短路径”的问题就是迪杰斯特拉算法要解决的核心问题。迪杰斯特拉算法听起来名字有点拗口但它的思想非常直观就是一种“贪心”的策略。你可以把它想象成一个谨慎的探险家从起点出发每次只探索并确认一条当前已知的、绝对最短的路径然后以这个新确认的据点为中心去更新它周围区域的路径信息一步步扩大自己的“安全区”直到抵达终点或者探索完所有地方。我刚开始学这个算法的时候总觉得它和生活中做决策很像。比如你要准备一场考试手头有好几门课要复习A、B、C、D但你时间有限。你可能会先花时间搞定那门最容易提分路径最短的课A搞定之后你发现因为掌握了A课的知识原来觉得很难的B课通过A课中转现在复习起来更快了于是你更新了对B课所需时间的估计。接着你再从剩下的课里挑出现在看来耗时最短的那门去攻克……如此循环直到安排好所有课的复习计划。迪杰斯特拉算法就是把这个“先易后难逐步优化”的过程用严格的数学和编程语言描述了出来。这个算法是由荷兰计算机科学家艾兹格·迪科斯彻在1956年提出的是图论和计算机科学中一个里程碑式的成果。它专门解决“单源最短路径”问题也就是说给定一个起点它能算出这个起点到图中所有其他点的最短距离。这里有个重要的前提图中边的“权值”可以理解为距离、时间、花费等不能是负数。因为如果存在负权边这个“贪心”的策略就可能失效你可能会因为眼前的小便宜而走上一条整体更差的路。对于有负权边的图我们需要请出另一位“高手”——贝尔曼-福特算法。2. 算法核心原理与图解一步步“扩张领土”理解了算法的生活化比喻我们再用更技术化的语言和图示来拆解它的步骤。算法的核心是维护两个集合和一个距离数组S集合已确定最短路径的顶点集合就像你已经完全探索清楚、百分百确定最短路径的“安全区”。最初这个集合里只有起点。U集合未确定最短路径的顶点集合这是待探索的“未知区域”包含了除起点外的所有顶点。dist数组最短距离估计数组记录从起点到每个顶点的当前已知最短距离。初始化时起点到自己的距离为0到直接相邻的顶点距离为边的权值到不直接相邻的顶点距离为“无穷大”在代码里我们用一个很大的数比如65535来表示。算法的每一步就是做下面这件事挑选新成员从U集合中选出那个dist值最小的顶点k。为什么选它因为从起点到其他任何未确定顶点的路径都必须经过S集合中的点“中转”。既然k是U中距离起点最近的那么不可能存在一条经由其他U中顶点再到k的、比当前dist[k]更短的路径了否则那条路径的中转点距离应该比k更小。所以dist[k]就是最终的最短距离可以把k从U移到S中。更新领地新成员k加入S后我们的“安全区”扩大了。这时候我们要以k为新的前沿看看能不能更新U中那些邻居的dist值。具体来说对于U中的每个顶点v如果k到v有边那么我们就检查dist[k] (k到v的边权)是否小于dist[v]。如果小于说明我们发现了一条经过k的、更短的到达v的路径于是更新dist[v]为这个更小的值同时记录下v的前驱节点是k方便最后回溯路径。循环往复重复步骤1和2直到U集合为空或者我们找到了目标终点的最短路径。让我们用一个超简单的图来走一遍流程。假设我们有4个城市A、B、C、D作为图的顶点之间的道路和距离权值如下A --6-- B | / | 2 3 1 | / | C --1-- DA到B距离6A到C距离2C到D距离1D到B距离1B到D距离3C到B距离3现在我们要找从A出发到所有城市的最短路径。初始化S {A}。dist[A]0, dist[B]6, dist[C]2, dist[D]∞A不直接到D。第一轮U中dist最小的是C值为2。将C加入S。更新通过C到Bdist[C]35小于dist[B]的6所以更新dist[B]5B的前驱记为C。通过C到Ddist[C]13小于dist[D]的∞更新dist[D]3D的前驱记为C。现在S{A, C}。第二轮U中dist最小的是D值为3。将D加入S。更新通过D到Bdist[D]14小于dist[B]的5所以更新dist[B]4B的前驱更新为D。现在S{A, C, D}。第三轮U中只剩下B值为4。将B加入S。没有需要更新的了。S{A, C, D, B}。最终结果A到B最短距离4路径A-C-D-BA到C最短距离2A到D最短距离3路径A-C-D。你看算法并没有一眼看穿全局而是一步一个脚印通过局部最优的选择最终得到了全局最优解。3. 数据结构设计如何用C语言描述图在动手写代码之前我们得先想好怎么在C语言里表示上面提到的“城市”和“道路”。最经典、也最直观的方法是使用邻接矩阵。我们可以定义一个结构体MGraph来表示一个图#define MAX_VEX 100 // 假设图最多有100个顶点 #define INF 65535 // 用一个很大的数代表“无穷远”表示两点间没有直接边 typedef struct { char vexs[MAX_VEX]; // 顶点数组用来存储顶点数据比如城市名A,B int arcs[MAX_VEX][MAX_VEX]; // 邻接矩阵存储边的权值 int vexNum, arcNum; // 图的当前顶点数和边数 } MGraph;这个arcs二维数组是关键。arcs[i][j]的值就代表顶点i到顶点j的边的权值。如果i和j之间没有直接的边我们就用INF来填充。对于无向图道路双向通行arcs[i][j]和arcs[j][i]的值应该相等对于有向图单行道它们可以不同。除了图本身我们还需要几个辅助数组来跑迪杰斯特拉算法int dist[MAX_VEX]; // 存储从源点到每个顶点的最短距离估计 int path[MAX_VEX]; // 存储最短路径上每个顶点的前一个顶点下标。比如 path[3]1表示到顶点3的最短路径上3的前一个点是1。 int final[MAX_VEX]; // 标记数组final[i]1 表示顶点i的最短路径已确定即已加入S集合0表示未确定。path数组非常有用它像一个路标链。当我们算法结束后如果想打印出从起点到顶点v的具体路径就可以从v开始根据path[v]找到上一个点再找上一个点的上一个点一直回溯到起点然后逆序输出就得到了完整路径。4. 手把手实现迪杰斯特拉算法的C语言代码理论说再多不如一行代码。下面我就结合详细的注释带你完整实现迪杰斯特拉算法。我们会把功能拆解成几个函数让结构更清晰。首先需要一个函数来根据顶点数据比如城市名找到它在vexs数组中的下标这个操作在创建图和查询时很常用// 查找顶点在顶点数组中的位置找不到返回-1 int LocateVex(MGraph *G, char v) { for (int i 0; i G-vexNum; i) { if (G-vexs[i] v) { return i; } } printf(错误顶点 %c 不存在\n, v); return -1; }接着我们来写一个创建图的函数。这里我实现的是无向图的创建如果你需要处理有向图只需要在输入边的时候只给arcs[start][end]赋值而不赋值arcs[end][start]即可。// 创建无向网带权无向图 void CreateMGraph(MGraph *G) { printf(请输入顶点数和边数格式顶点数 边数: ); scanf(%d %d, (G-vexNum), (G-arcNum)); printf(请依次输入 %d 个顶点的信息例如A B C ...: , G-vexNum); for (int i 0; i G-vexNum; i) { scanf( %c, (G-vexs[i])); // 注意%c前的空格用于吸收换行符 } // 初始化邻接矩阵所有边权初始为INF自己到自己的距离为0 for (int i 0; i G-vexNum; i) { for (int j 0; j G-vexNum; j) { if (i j) { G-arcs[i][j] 0; } else { G-arcs[i][j] INF; } } } printf(请依次输入 %d 条边的信息格式起点 终点 权值:\n, G-arcNum); char v1, v2; int weight; for (int k 0; k G-arcNum; k) { scanf( %c %c %d, v1, v2, weight); int i LocateVex(G, v1); int j LocateVex(G, v2); if (i ! -1 j ! -1) { G-arcs[i][j] weight; G-arcs[j][i] weight; // 无向图矩阵对称 } else { printf(输入顶点有误请重新输入本条边。\n); k--; // 重新输入本条边 } } printf(图创建成功\n); }好了重头戏来了迪杰斯特拉算法的核心函数// Dijkstra算法求单源最短路径 // G: 图 // v0: 源点的下标 // dist: 存放最短路径长度的数组 // path: 存放前驱顶点的数组 void Dijkstra(MGraph G, int v0, int dist[], int path[]) { int final[MAX_VEX]; // 标记顶点是否已找到最短路径 int i, j, k, min; // 1. 初始化 for (i 0; i G.vexNum; i) { final[i] 0; // 所有顶点初始状态均为未找到最短路径 dist[i] G.arcs[v0][i]; // 将源点v0到各点的直接距离存入dist if (dist[i] INF) { path[i] v0; // 如果v0能直接到达i则i的前驱设为v0 } else { path[i] -1; // 否则前驱设为-1表示不可达或尚未知 } } // 源点自身初始化 final[v0] 1; dist[v0] 0; path[v0] -1; // 源点没有前驱 // 2. 主循环每次找出一个顶点的最短路径 for (i 1; i G.vexNum; i) { // 循环n-1次找剩下n-1个点的最短路径 min INF; k -1; // 2.1 在未确定的顶点集合中寻找dist最小的顶点k for (j 0; j G.vexNum; j) { if (!final[j] dist[j] min) { min dist[j]; k j; // k记录当前找到的最小距离顶点的下标 } } if (k -1) { // 如果没有找到说明剩下的顶点都与源点不连通 break; } final[k] 1; // 将顶点k加入已确定集合 // 2.2 以k为中间点更新未确定顶点的dist和path for (j 0; j G.vexNum; j) { // 如果顶点j未确定且k到j有边且经过k到j比原来更近 if (!final[j] G.arcs[k][j] INF) { if (min G.arcs[k][j] dist[j]) { dist[j] min G.arcs[k][j]; path[j] k; // 更新j的前驱为k } } } } }最后我们需要一个函数来打印最短路径。由于path数组记录的是前驱所以打印时需要从终点回溯到起点我们可以用栈或者递归来实现逆序输出。这里我用一个简单的方法先计算路径长度再正向打印。// 打印从源点到顶点v的最短路径 void PrintPath(MGraph G, int v0, int v, int path[]) { int stack[MAX_VEX], top -1; // 用一个数组模拟栈 int temp v; // 从终点v开始沿着前驱路径压栈直到源点v0其path为-1 while (temp ! -1) { stack[top] temp; temp path[temp]; } // 出栈打印即为从源点到终点的正确顺序 printf(路径: %c, G.vexs[stack[top]]); for (int i top - 1; i 0; i--) { printf( - %c, G.vexs[stack[i]]); } printf(\n); }把上面的函数组合起来就是一个完整的程序了#include stdio.h #include stdlib.h #define MAX_VEX 100 #define INF 65535 // ... 这里插入上面定义的 MGraph 结构体、LocateVex、CreateMGraph、Dijkstra、PrintPath 函数 ... int main() { MGraph G; int dist[MAX_VEX], path[MAX_VEX]; char startVex; int startIndex; CreateMGraph(G); printf(\n请输入源点顶点例如A: ); scanf( %c, startVex); startIndex LocateVex(G, startVex); if (startIndex -1) { printf(源点不存在\n); return 0; } Dijkstra(G, startIndex, dist, path); printf(\n从顶点 %c 到其他各顶点的最短路径信息如下\n, startVex); printf(顶点\t最短距离\t路径\n); for (int i 0; i G.vexNum; i) { if (i ! startIndex) { printf(%c\t, G.vexs[i]); if (dist[i] INF) { printf(%d\t\t, dist[i]); PrintPath(G, startIndex, i, path); } else { printf(不可达\t\t\n); } } } return 0; }你可以编译运行这个程序输入我们之前例子中的图数据4个顶点A,B,C,D5条边源点设为A看看输出结果是不是和我们手动计算的一致。通过自己敲一遍代码并运行调试你会对算法的每一步有更深刻的理解。5. 算法分析与实战要点实现完代码我们回过头来分析一下这个算法的性能和一些需要注意的坑。时间复杂度我们代码中有两层嵌套的for循环外层循环n-1次n为顶点数内层有两个并列的循环都是遍历所有顶点n次。所以总的时间复杂度是O(n²)。这在顶点数不多的时候几百上千完全够用。但如果图的规模非常大比如几万、几十万个顶点这个复杂度就有点吃力了。这时候可以考虑使用**优先队列最小堆**来优化寻找dist最小值的步骤可以将时间复杂度降到O((ne)log n)其中e是边数。这在稀疏图边数远小于n²中效率提升非常明显。不过那就是更进阶的优化了掌握了基础版本理解优化版本会容易很多。空间复杂度主要是存储邻接矩阵的O(n²)以及几个辅助数组的O(n)。如果图非常稀疏用邻接表存储可以节省大量空间但迪杰斯特拉算法的实现也会稍复杂一些。几个实战中容易踩的坑无穷大的取值INF不能乱设。要确保它大于图中任何可能路径的权值之和。通常用0x3f3f3f3f约10^9或者INT_MAX/2防止加法溢出是不错的选择。我上面用的65535对于小权值图没问题。负权边这是迪杰斯特拉算法的“天敌”。再次强调算法不能处理带有负权边的图。因为它的贪心策略基于一个假设一旦一个顶点被加入S集合其最短距离就确定了。如果存在负权边这个假设就不成立因为后面可能通过一条负权边让路径变得更短。如果你不确定图中是否有负权保险起见就用贝尔曼-福特算法。路径打印path数组存储的是前驱节点打印路径时需要反向回溯。我上面用栈来反转顺序是一个清晰的方法。你也可以用递归但要注意递归深度可能带来的栈溢出问题。图的存储方式我们用的是邻接矩阵对于稠密图很合适。但如果你的图边很少稀疏图邻接矩阵会浪费大量空间。在实际项目或算法竞赛中根据图的特点选择邻接矩阵或邻接表或链式前向星是必备技能。6. 从理解到应用我能用迪杰斯特拉算法做什么学了一个算法总得知道它能干嘛不然很容易就忘了。迪杰斯特拉算法的应用场景其实非常广泛远远不止于地图导航。网络路由协议像OSPF开放最短路径优先协议路由器之间交换链路状态信息构建网络拓扑图然后每个路由器都用迪杰斯特拉算法计算到自己到网络中所有其他路由器的最短路径从而决定数据包怎么转发。这是它最经典的应用之一。交通规划除了汽车导航也用于航班航线规划、铁路调度等这里的“权值”可能是时间、成本或者距离。游戏开发在策略游戏或RPG游戏中AI需要计算单位移动到目标位置的最短路径如果地形有不同的移动代价比如沼泽走得慢平原走得快迪杰斯特拉算法就能派上用场。虽然游戏里更常用A算法但A可以看作是迪杰斯特拉算法的启发式优化版本。社交网络可以计算两个人之间的“最短关联路径”比如通过最少共同好友认识。这时边的权值可以设为1每经过一个朋友距离加1。项目关键路径分析在项目管理中虽然更常用PERT/CPM但其思想与最短路径有相通之处。我印象比较深的一次使用是在一个简单的网络模拟器项目中。我需要模拟几个节点之间的数据包转发每个链路有不同的延迟。用迪杰斯特拉算法预先计算好最短路径树然后让数据包沿着这个树转发非常简单就实现了基础的路由功能。当你亲手把一个算法用在解决实际问题上时那种成就感是完全不一样的。最后想说的是学习算法就像学武功理解了心法原理之后一定要多练招式代码实现。不要满足于看懂要自己把代码敲出来用不同的测试数据去运行甚至尝试去修改它、优化它。比如你可以试着把邻接矩阵改成邻接表来实现或者尝试实现一下输出具体路径的功能。踩过几个坑之后你对这个算法的理解才会真正牢固。迪杰斯特拉算法是图论算法的一个基石掌握好它对你后续学习其他更复杂的图算法比如Floyd、A*、最小生成树会有非常大的帮助。