1. 从地图导航到网络路由为什么我们需要最短路径算法想象一下你打开手机地图输入“家”和“公司”App瞬间为你规划出一条耗时最短或距离最短的路线。这个看似简单的功能背后核心引擎之一就是最短路径算法。而在众多算法中Dijkstra算法因其思想直观、实现相对简单成为了解决“单元最短路径问题”的经典基石。无论是网络数据包的路由选择、物流配送的路径优化还是游戏中的NPC寻路其身影无处不在。今天我们不谈那些封装好的库和复杂的优化变种就回归最本质的形态手把手拆解并实现一个“朴素版”的Dijkstra算法。我会带你从零理解它的每一步为什么这么做并分享在实现过程中那些容易踩坑的细节和调试心得。无论你是正在学习《数据结构与算法》的学生还是需要在实际项目中应用基础图算法的开发者这篇内容都能让你不仅“写得出来”更能“懂得透彻”。2. 问题定义与算法核心思想拆解在深入代码之前我们必须清晰地界定我们要解决的问题并理解Dijkstra是如何思考的。这比直接记忆步骤重要得多。2.1 什么是“单元最短路径问题”我们有一个带权有向图无向图可以视为双向有向图。图由顶点和边组成每条边都有一个非负的权重可以代表距离、时间、成本等。给定一个源点我们需要找出从该源点到图中所有其他顶点的最短路径及其长度。这里有几个关键约束和概念非负权边这是Dijkstra算法正确性的前提。如果存在负权边算法可能得出错误结果这时需要考虑Bellman-Ford或SPFA算法。“最短”的定义指的是路径上所有边的权重之和最小。松弛操作这是所有最短路径算法的核心操作。简单说就是发现一条从源点到顶点B的更短路径时就更新B当前的最短距离估计。2.2 Dijkstra的贪心策略为什么它是对的Dijkstra算法的思想非常“贪心”。它维护两个集合已确定最短路径的顶点集合S和未确定的顶点集合T。它的核心洞察是从源点到当前T集合中距离估计最小的那个顶点其最短路径就已经被确定了。我们可以用一个生活化的类比来理解假设你要逐步点亮一张黑暗地图上的所有城市顶点你站在首都源点。每次你都派出速度最快的信使去往距离你最近且未被点亮的那个城市。当信使到达时你就点亮那个城市加入S集并认为从首都到该城市的最短路径就是信使走过的这条路。接着从这个新点亮的城市你可以派出新的信使去更新它周边未点亮城市的距离这就是松弛。重复这个过程直到所有城市都被点亮。为什么这个贪心选择是对的因为所有边的权重都是非负的。既然你每次选的都是T集中离源点最近的点那么从源点出发经过其他T集中的点再绕到该点由于绕路会增加非负的权重所以总距离不可能比当前直达或已找到的路径更短。这个性质保证了算法的正确性。3. 朴素版Dijkstra的逐步实现与详解“朴素版”通常指的是使用最简单的数据结构——邻接矩阵或邻接表来存储图并使用线性扫描的方式来寻找T集合中的最小值。我们以邻接矩阵为例因为它最直观。假设图有n个顶点编号从0到n-1。3.1 数据结构定义与初始化首先我们需要定义几个关键的数组int graph[n][n]邻接矩阵。graph[i][j]表示从顶点i到j的边的权重。如果两点间没有直接边通常用一个很大的数如INT_MAX或0x3f3f3f3f表示“无穷大”。int dist[n]记录从源点src到每个顶点的当前最短距离估计。初始化时dist[src] 0其他均为“无穷大”。bool visited[n]标记顶点是否已加入S集即是否已确定最短路径。初始化全为false。int prev[n]可选用于回溯还原具体路径。prev[v]记录在最短路径上顶点v的前驱顶点。初始化代码如下以C为例#include climits #include vector using namespace std; const int INF 0x3f3f3f3f; // 用一个较大的数代表无穷大避免加法溢出 void dijkstra(vectorvectorint graph, int src, int n) { vectorint dist(n, INF); vectorbool visited(n, false); vectorint prev(n, -1); // -1表示无前驱 dist[src] 0; // 算法主循环开始 }注意为什么用0x3f3f3f3f因为它大约等于10^9在通常的题目范围内足够大。更重要的是两个0x3f3f3f3f相加不会溢出到负数仍在int范围内而INT_MAX相加则会溢出导致错误这在松弛操作中可能发生。3.2 算法主循环寻找、松弛与标记主循环要进行n次每次从T集未访问顶点中找到一个dist最小的顶点u。for (int i 0; i n; i) { // 步骤1在未访问顶点中找到dist最小的顶点u int u -1; int minDist INF; for (int j 0; j n; j) { if (!visited[j] dist[j] minDist) { minDist dist[j]; u j; } } // 如果找不到说明剩下的顶点不可达算法可以提前结束 if (u -1) break; // 步骤2将u标记为已访问加入S集 visited[u] true; // 步骤3松弛操作——以u为中介点更新其邻居的距离 for (int v 0; v n; v) { // 确保u到v有边且v未被访问 if (!visited[v] graph[u][v] ! INF) { int newDist dist[u] graph[u][v]; if (newDist dist[v]) { dist[v] newDist; prev[v] u; // 记录路径 } } } }逐行解读与心法寻找最小dist的顶点这是“朴素”的体现我们用了一个O(n)的线性扫描。对于稠密图边数接近n^2这个开销可以接受因为整体复杂度是O(n^2)。但对于稀疏图这就很低效了此时应该使用优先队列堆优化复杂度可降至O((nm)log n)。标记visited[u] true这一步至关重要。一旦将u标记为已访问意味着从源点到u的最短距离已经最终确定后续的松弛操作将不再考虑以u为终点只考虑以u为跳板。这是Dijkstra算法区别于其他算法如处理负权边的Bellman-Ford的关键。松弛操作这是算法的动力来源。newDist dist[u] graph[u][v]的含义是“如果我从源点先走到u最短距离dist[u]再从u直接走到v这条新路径的总长度是多少”如果它小于v当前记录的最短估计dist[v]那么我们就找到了一个更优的路径于是更新dist[v]并记录v是从u过来的prev[v] u。3.3 路径还原算法结束后dist数组存储了从源点到所有点的最短距离。如果我们还需要知道具体怎么走的就需要通过prev数组回溯。void printPath(int dest, const vectorint prev) { if (prev[dest] -1) { cout dest; return; } printPath(prev[dest], prev); cout - dest; } // 例如打印从src到顶点t的路径 // printPath(t, prev);4. 复杂度分析与“朴素”二字的代价我们来分析一下这个版本的时间复杂度和空间复杂度这能让我们明白在什么场景下该用这个版本以及何时需要考虑优化。时间复杂度外层循环执行n次。每次循环中内层有两个主要操作线性查找最小distO(n)。松弛所有邻居在邻接矩阵中我们需要遍历所有n个顶点来检查是否为邻居因此也是O(n)。 所以总时间复杂度为O(n^2)。这里的n是顶点数。空间复杂度主要开销在于存储邻接矩阵graph[n][n]因此是O(n^2)。如果使用邻接表空间复杂度可降至O(nm)其中m是边数。“朴素”的代价与适用场景 “朴素”主要体现在用O(n)的线性查找来获取最小值以及使用O(n^2)空间的邻接矩阵。这使得它在顶点数很大例如n 10^4时性能会急剧下降。因此朴素版Dijkstra适用于稠密图当边数m接近n^2时使用邻接矩阵和O(n^2)的算法在常数时间上可能有优势且代码简单。顶点数较少例如在算法竞赛中n在500~1000左右O(n^2)是完全可接受的。教学与理解这是理解Dijkstra思想最直观的方式。对于顶点数多、边数少的稀疏图例如社交网络、道路网络我们几乎一定会使用“堆优化版Dijkstra”将查找最小值的复杂度从O(n)降至O(log n)。5. 从理论到实践常见坑点与调试心得纸上得来终觉浅自己实现一遍总会遇到各种问题。下面是我在多次实现和调试中总结的几个关键点。5.1 无穷大值的设定与溢出问题这是一个非常经典的坑。如前所述不能简单使用INT_MAX。// 错误示范 const int INF INT_MAX; if (dist[u] graph[u][v] dist[v]) ... // 如果dist[u]是INF加法会导致负溢出 // 正确做法 const int INF 0x3f3f3f3f; // 或者在确定不会进行加法比较的场景下用INT_MAX/2 const int INF INT_MAX / 2;心得我习惯用0x3f3f3f3f它不仅满足“足够大”和“相加不溢出”而且用memset(graph, 0x3f, sizeof(graph))可以快速将整个数组初始化为这个值因为0x3f的字节模式很适合。5.2 “已访问”标记的时机与重要性一定要在松弛其所有邻居之前将顶点u标记为visited[u] true。顺序不能颠倒。因为一旦标记该顶点的dist值就锁定了后续不会再被更新。如果先松弛再标记逻辑上虽然可能不影响结果因为松弛操作是基于当前dist[u]但符合算法语义也更安全。更严重的错误是忘记标记。如果忘记标记算法可能会在后续的循环中再次选中同一个顶点u因为它的dist仍然是最小的这将导致无限循环或错误结果。5.3 处理不连通图我们的代码中有一个判断if (u -1) break;。这行代码就是用来处理非连通图的。当所有未访问顶点的dist都是INF时意味着剩下的顶点都无法从源点到达循环可以提前终止。如果不加这个判断u将保持-1在后续访问graph[u][v]时会导致数组越界。5.4 邻接矩阵与邻接表的选择我们一直用邻接矩阵举例但对于稀疏图这会造成巨大的空间浪费和无效遍历松弛时需要检查所有n个顶点即使大部分边不存在。邻接表实现的关键改动数据结构vectorvectorpairint, int adj(n)adj[u]存储所有从u出发的边(v, weight)。松弛部分不再遍历所有顶点而是只遍历adj[u]这个链表。for (const auto edge : adj[u]) { int v edge.first; int w edge.second; if (!visited[v] dist[u] w dist[v]) { dist[v] dist[u] w; prev[v] u; } }即使使用朴素的线性查找最小dist改用邻接表也能将内层松弛的复杂度从O(n)降到O(degree(u))对于稀疏图是一大提升。当然结合堆优化才是完全体。6. 完整可运行代码示例与测试让我们整合一个完整的、使用邻接矩阵的朴素版Dijkstra并附上一个测试用例。#include iostream #include vector #include climits using namespace std; const int INF 0x3f3f3f3f; void dijkstra(vectorvectorint graph, int src, vectorint dist, vectorint prev) { int n graph.size(); dist.assign(n, INF); prev.assign(n, -1); vectorbool visited(n, false); dist[src] 0; for (int i 0; i n; i) { // 1. 找到未访问顶点中dist最小的 int u -1; int minDist INF; for (int j 0; j n; j) { if (!visited[j] dist[j] minDist) { minDist dist[j]; u j; } } if (u -1) break; // 剩余顶点不可达 // 2. 标记为已访问 visited[u] true; // 3. 松弛操作 for (int v 0; v n; v) { if (!visited[v] graph[u][v] ! INF) { int newDist dist[u] graph[u][v]; if (newDist dist[v]) { dist[v] newDist; prev[v] u; } } } } } void printPath(int v, const vectorint prev) { if (prev[v] -1) { cout v; return; } printPath(prev[v], prev); cout - v; } int main() { int n 5; // 5个顶点 vectorvectorint graph(n, vectorint(n, INF)); // 初始化自己到自己的距离为0 for (int i 0; i n; i) graph[i][i] 0; // 添加边 (u, v, weight) graph[0][1] 10; graph[0][3] 5; graph[1][2] 1; graph[1][3] 2; graph[2][4] 4; graph[3][1] 3; graph[3][2] 9; graph[3][4] 2; graph[4][0] 7; graph[4][2] 6; int src 0; vectorint dist, prev; dijkstra(graph, src, dist, prev); cout 从顶点 src 到各顶点的最短距离及路径 endl; for (int i 0; i n; i) { if (dist[i] INF) { cout 顶点 i : 不可达 endl; } else { cout 顶点 i : 距离 dist[i] , 路径 ; printPath(i, prev); cout endl; } } return 0; }测试结果分析 以上图为例从顶点0出发算法应该计算出到顶点1路径 0-3-1距离 8。到顶点3路径 0-3距离 5。到顶点4路径 0-3-4距离 7。到顶点2路径 0-3-1-2距离 9。 运行代码可以验证这些结果。手动模拟一遍算法的执行过程对照输出是理解算法每一步状态变化的最佳方式。7. 算法变种、局限与进阶方向掌握了朴素版就像是学会了驾驶手动挡汽车理解了最基础的原理。但实际应用中我们更多是开自动挡优化版。了解其局限和变种能帮助你在不同场景下做出正确选择。7.1 主要局限不能处理负权边这是由其贪心性质决定的。如果存在负权边之前被标记为“已确定”的顶点可能通过一条包含负权边的路径变得更短从而破坏算法基础。对于含负权边的图需要使用Bellman-Ford算法。时间复杂度固定为O(n^2)对于大规模稀疏图效率低下。7.2 经典优化堆优先队列优化这是必须掌握的进阶技能。思路很简单我们用一个小顶堆优先队列来存储(距离, 顶点)对这样每次获取距离最小的顶点只需要O(log n)的时间。// 伪代码思路 priority_queuepairint, int, vectorpairint, int, greater pq; // 最小堆 pq.emplace(0, src); dist[src] 0; while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d dist[u]) continue; // 关键过滤掉堆中过时的、冗余的条目 for (auto [v, w] : adj[u]) { if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.emplace(dist[v], v); // 可能有重复顶点入堆 } } }这个版本的时间复杂度是O((nm) log n)空间复杂度O(m)非常适合稀疏图。注意代码中的if (d dist[u]) continue;这一行这是堆优化Dijkstra的灵魂所在用于处理同一顶点因多次松弛而产生的多个不同距离的条目确保我们只处理最新的那个。7.3 与其他算法的简单对比Floyd-Warshall解决“所有顶点对”之间的最短路径时间复杂度O(n^3)。当需要计算图中任意两点间最短路径时使用编码极其简单。Bellman-Ford能处理负权边并能检测负权环时间复杂度O(n*m)。比Dijkstra慢但适用场景不同。A*搜索在Dijkstra基础上加入了启发式函数用于在知道终点位置信息的场景下如地图寻路大幅加速搜索但它需要设计一个合理的启发函数。理解朴素Dijkstra是通往这些更高级算法和优化版本的坚实桥梁。它那清晰的贪心思想和松弛操作是图论中最优美的概念之一。下次当你使用导航软件时或许会会心一笑知道其中正运行着成千上万次Dijkstra算法的变体为你计算着最优路线。
1. 从地图导航到网络路由为什么我们需要最短路径算法想象一下你打开手机地图输入“家”和“公司”App瞬间为你规划出一条耗时最短或距离最短的路线。这个看似简单的功能背后核心引擎之一就是最短路径算法。而在众多算法中Dijkstra算法因其思想直观、实现相对简单成为了解决“单元最短路径问题”的经典基石。无论是网络数据包的路由选择、物流配送的路径优化还是游戏中的NPC寻路其身影无处不在。今天我们不谈那些封装好的库和复杂的优化变种就回归最本质的形态手把手拆解并实现一个“朴素版”的Dijkstra算法。我会带你从零理解它的每一步为什么这么做并分享在实现过程中那些容易踩坑的细节和调试心得。无论你是正在学习《数据结构与算法》的学生还是需要在实际项目中应用基础图算法的开发者这篇内容都能让你不仅“写得出来”更能“懂得透彻”。2. 问题定义与算法核心思想拆解在深入代码之前我们必须清晰地界定我们要解决的问题并理解Dijkstra是如何思考的。这比直接记忆步骤重要得多。2.1 什么是“单元最短路径问题”我们有一个带权有向图无向图可以视为双向有向图。图由顶点和边组成每条边都有一个非负的权重可以代表距离、时间、成本等。给定一个源点我们需要找出从该源点到图中所有其他顶点的最短路径及其长度。这里有几个关键约束和概念非负权边这是Dijkstra算法正确性的前提。如果存在负权边算法可能得出错误结果这时需要考虑Bellman-Ford或SPFA算法。“最短”的定义指的是路径上所有边的权重之和最小。松弛操作这是所有最短路径算法的核心操作。简单说就是发现一条从源点到顶点B的更短路径时就更新B当前的最短距离估计。2.2 Dijkstra的贪心策略为什么它是对的Dijkstra算法的思想非常“贪心”。它维护两个集合已确定最短路径的顶点集合S和未确定的顶点集合T。它的核心洞察是从源点到当前T集合中距离估计最小的那个顶点其最短路径就已经被确定了。我们可以用一个生活化的类比来理解假设你要逐步点亮一张黑暗地图上的所有城市顶点你站在首都源点。每次你都派出速度最快的信使去往距离你最近且未被点亮的那个城市。当信使到达时你就点亮那个城市加入S集并认为从首都到该城市的最短路径就是信使走过的这条路。接着从这个新点亮的城市你可以派出新的信使去更新它周边未点亮城市的距离这就是松弛。重复这个过程直到所有城市都被点亮。为什么这个贪心选择是对的因为所有边的权重都是非负的。既然你每次选的都是T集中离源点最近的点那么从源点出发经过其他T集中的点再绕到该点由于绕路会增加非负的权重所以总距离不可能比当前直达或已找到的路径更短。这个性质保证了算法的正确性。3. 朴素版Dijkstra的逐步实现与详解“朴素版”通常指的是使用最简单的数据结构——邻接矩阵或邻接表来存储图并使用线性扫描的方式来寻找T集合中的最小值。我们以邻接矩阵为例因为它最直观。假设图有n个顶点编号从0到n-1。3.1 数据结构定义与初始化首先我们需要定义几个关键的数组int graph[n][n]邻接矩阵。graph[i][j]表示从顶点i到j的边的权重。如果两点间没有直接边通常用一个很大的数如INT_MAX或0x3f3f3f3f表示“无穷大”。int dist[n]记录从源点src到每个顶点的当前最短距离估计。初始化时dist[src] 0其他均为“无穷大”。bool visited[n]标记顶点是否已加入S集即是否已确定最短路径。初始化全为false。int prev[n]可选用于回溯还原具体路径。prev[v]记录在最短路径上顶点v的前驱顶点。初始化代码如下以C为例#include climits #include vector using namespace std; const int INF 0x3f3f3f3f; // 用一个较大的数代表无穷大避免加法溢出 void dijkstra(vectorvectorint graph, int src, int n) { vectorint dist(n, INF); vectorbool visited(n, false); vectorint prev(n, -1); // -1表示无前驱 dist[src] 0; // 算法主循环开始 }注意为什么用0x3f3f3f3f因为它大约等于10^9在通常的题目范围内足够大。更重要的是两个0x3f3f3f3f相加不会溢出到负数仍在int范围内而INT_MAX相加则会溢出导致错误这在松弛操作中可能发生。3.2 算法主循环寻找、松弛与标记主循环要进行n次每次从T集未访问顶点中找到一个dist最小的顶点u。for (int i 0; i n; i) { // 步骤1在未访问顶点中找到dist最小的顶点u int u -1; int minDist INF; for (int j 0; j n; j) { if (!visited[j] dist[j] minDist) { minDist dist[j]; u j; } } // 如果找不到说明剩下的顶点不可达算法可以提前结束 if (u -1) break; // 步骤2将u标记为已访问加入S集 visited[u] true; // 步骤3松弛操作——以u为中介点更新其邻居的距离 for (int v 0; v n; v) { // 确保u到v有边且v未被访问 if (!visited[v] graph[u][v] ! INF) { int newDist dist[u] graph[u][v]; if (newDist dist[v]) { dist[v] newDist; prev[v] u; // 记录路径 } } } }逐行解读与心法寻找最小dist的顶点这是“朴素”的体现我们用了一个O(n)的线性扫描。对于稠密图边数接近n^2这个开销可以接受因为整体复杂度是O(n^2)。但对于稀疏图这就很低效了此时应该使用优先队列堆优化复杂度可降至O((nm)log n)。标记visited[u] true这一步至关重要。一旦将u标记为已访问意味着从源点到u的最短距离已经最终确定后续的松弛操作将不再考虑以u为终点只考虑以u为跳板。这是Dijkstra算法区别于其他算法如处理负权边的Bellman-Ford的关键。松弛操作这是算法的动力来源。newDist dist[u] graph[u][v]的含义是“如果我从源点先走到u最短距离dist[u]再从u直接走到v这条新路径的总长度是多少”如果它小于v当前记录的最短估计dist[v]那么我们就找到了一个更优的路径于是更新dist[v]并记录v是从u过来的prev[v] u。3.3 路径还原算法结束后dist数组存储了从源点到所有点的最短距离。如果我们还需要知道具体怎么走的就需要通过prev数组回溯。void printPath(int dest, const vectorint prev) { if (prev[dest] -1) { cout dest; return; } printPath(prev[dest], prev); cout - dest; } // 例如打印从src到顶点t的路径 // printPath(t, prev);4. 复杂度分析与“朴素”二字的代价我们来分析一下这个版本的时间复杂度和空间复杂度这能让我们明白在什么场景下该用这个版本以及何时需要考虑优化。时间复杂度外层循环执行n次。每次循环中内层有两个主要操作线性查找最小distO(n)。松弛所有邻居在邻接矩阵中我们需要遍历所有n个顶点来检查是否为邻居因此也是O(n)。 所以总时间复杂度为O(n^2)。这里的n是顶点数。空间复杂度主要开销在于存储邻接矩阵graph[n][n]因此是O(n^2)。如果使用邻接表空间复杂度可降至O(nm)其中m是边数。“朴素”的代价与适用场景 “朴素”主要体现在用O(n)的线性查找来获取最小值以及使用O(n^2)空间的邻接矩阵。这使得它在顶点数很大例如n 10^4时性能会急剧下降。因此朴素版Dijkstra适用于稠密图当边数m接近n^2时使用邻接矩阵和O(n^2)的算法在常数时间上可能有优势且代码简单。顶点数较少例如在算法竞赛中n在500~1000左右O(n^2)是完全可接受的。教学与理解这是理解Dijkstra思想最直观的方式。对于顶点数多、边数少的稀疏图例如社交网络、道路网络我们几乎一定会使用“堆优化版Dijkstra”将查找最小值的复杂度从O(n)降至O(log n)。5. 从理论到实践常见坑点与调试心得纸上得来终觉浅自己实现一遍总会遇到各种问题。下面是我在多次实现和调试中总结的几个关键点。5.1 无穷大值的设定与溢出问题这是一个非常经典的坑。如前所述不能简单使用INT_MAX。// 错误示范 const int INF INT_MAX; if (dist[u] graph[u][v] dist[v]) ... // 如果dist[u]是INF加法会导致负溢出 // 正确做法 const int INF 0x3f3f3f3f; // 或者在确定不会进行加法比较的场景下用INT_MAX/2 const int INF INT_MAX / 2;心得我习惯用0x3f3f3f3f它不仅满足“足够大”和“相加不溢出”而且用memset(graph, 0x3f, sizeof(graph))可以快速将整个数组初始化为这个值因为0x3f的字节模式很适合。5.2 “已访问”标记的时机与重要性一定要在松弛其所有邻居之前将顶点u标记为visited[u] true。顺序不能颠倒。因为一旦标记该顶点的dist值就锁定了后续不会再被更新。如果先松弛再标记逻辑上虽然可能不影响结果因为松弛操作是基于当前dist[u]但符合算法语义也更安全。更严重的错误是忘记标记。如果忘记标记算法可能会在后续的循环中再次选中同一个顶点u因为它的dist仍然是最小的这将导致无限循环或错误结果。5.3 处理不连通图我们的代码中有一个判断if (u -1) break;。这行代码就是用来处理非连通图的。当所有未访问顶点的dist都是INF时意味着剩下的顶点都无法从源点到达循环可以提前终止。如果不加这个判断u将保持-1在后续访问graph[u][v]时会导致数组越界。5.4 邻接矩阵与邻接表的选择我们一直用邻接矩阵举例但对于稀疏图这会造成巨大的空间浪费和无效遍历松弛时需要检查所有n个顶点即使大部分边不存在。邻接表实现的关键改动数据结构vectorvectorpairint, int adj(n)adj[u]存储所有从u出发的边(v, weight)。松弛部分不再遍历所有顶点而是只遍历adj[u]这个链表。for (const auto edge : adj[u]) { int v edge.first; int w edge.second; if (!visited[v] dist[u] w dist[v]) { dist[v] dist[u] w; prev[v] u; } }即使使用朴素的线性查找最小dist改用邻接表也能将内层松弛的复杂度从O(n)降到O(degree(u))对于稀疏图是一大提升。当然结合堆优化才是完全体。6. 完整可运行代码示例与测试让我们整合一个完整的、使用邻接矩阵的朴素版Dijkstra并附上一个测试用例。#include iostream #include vector #include climits using namespace std; const int INF 0x3f3f3f3f; void dijkstra(vectorvectorint graph, int src, vectorint dist, vectorint prev) { int n graph.size(); dist.assign(n, INF); prev.assign(n, -1); vectorbool visited(n, false); dist[src] 0; for (int i 0; i n; i) { // 1. 找到未访问顶点中dist最小的 int u -1; int minDist INF; for (int j 0; j n; j) { if (!visited[j] dist[j] minDist) { minDist dist[j]; u j; } } if (u -1) break; // 剩余顶点不可达 // 2. 标记为已访问 visited[u] true; // 3. 松弛操作 for (int v 0; v n; v) { if (!visited[v] graph[u][v] ! INF) { int newDist dist[u] graph[u][v]; if (newDist dist[v]) { dist[v] newDist; prev[v] u; } } } } } void printPath(int v, const vectorint prev) { if (prev[v] -1) { cout v; return; } printPath(prev[v], prev); cout - v; } int main() { int n 5; // 5个顶点 vectorvectorint graph(n, vectorint(n, INF)); // 初始化自己到自己的距离为0 for (int i 0; i n; i) graph[i][i] 0; // 添加边 (u, v, weight) graph[0][1] 10; graph[0][3] 5; graph[1][2] 1; graph[1][3] 2; graph[2][4] 4; graph[3][1] 3; graph[3][2] 9; graph[3][4] 2; graph[4][0] 7; graph[4][2] 6; int src 0; vectorint dist, prev; dijkstra(graph, src, dist, prev); cout 从顶点 src 到各顶点的最短距离及路径 endl; for (int i 0; i n; i) { if (dist[i] INF) { cout 顶点 i : 不可达 endl; } else { cout 顶点 i : 距离 dist[i] , 路径 ; printPath(i, prev); cout endl; } } return 0; }测试结果分析 以上图为例从顶点0出发算法应该计算出到顶点1路径 0-3-1距离 8。到顶点3路径 0-3距离 5。到顶点4路径 0-3-4距离 7。到顶点2路径 0-3-1-2距离 9。 运行代码可以验证这些结果。手动模拟一遍算法的执行过程对照输出是理解算法每一步状态变化的最佳方式。7. 算法变种、局限与进阶方向掌握了朴素版就像是学会了驾驶手动挡汽车理解了最基础的原理。但实际应用中我们更多是开自动挡优化版。了解其局限和变种能帮助你在不同场景下做出正确选择。7.1 主要局限不能处理负权边这是由其贪心性质决定的。如果存在负权边之前被标记为“已确定”的顶点可能通过一条包含负权边的路径变得更短从而破坏算法基础。对于含负权边的图需要使用Bellman-Ford算法。时间复杂度固定为O(n^2)对于大规模稀疏图效率低下。7.2 经典优化堆优先队列优化这是必须掌握的进阶技能。思路很简单我们用一个小顶堆优先队列来存储(距离, 顶点)对这样每次获取距离最小的顶点只需要O(log n)的时间。// 伪代码思路 priority_queuepairint, int, vectorpairint, int, greater pq; // 最小堆 pq.emplace(0, src); dist[src] 0; while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d dist[u]) continue; // 关键过滤掉堆中过时的、冗余的条目 for (auto [v, w] : adj[u]) { if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.emplace(dist[v], v); // 可能有重复顶点入堆 } } }这个版本的时间复杂度是O((nm) log n)空间复杂度O(m)非常适合稀疏图。注意代码中的if (d dist[u]) continue;这一行这是堆优化Dijkstra的灵魂所在用于处理同一顶点因多次松弛而产生的多个不同距离的条目确保我们只处理最新的那个。7.3 与其他算法的简单对比Floyd-Warshall解决“所有顶点对”之间的最短路径时间复杂度O(n^3)。当需要计算图中任意两点间最短路径时使用编码极其简单。Bellman-Ford能处理负权边并能检测负权环时间复杂度O(n*m)。比Dijkstra慢但适用场景不同。A*搜索在Dijkstra基础上加入了启发式函数用于在知道终点位置信息的场景下如地图寻路大幅加速搜索但它需要设计一个合理的启发函数。理解朴素Dijkstra是通往这些更高级算法和优化版本的坚实桥梁。它那清晰的贪心思想和松弛操作是图论中最优美的概念之一。下次当你使用导航软件时或许会会心一笑知道其中正运行着成千上万次Dijkstra算法的变体为你计算着最优路线。
