1. 项目概述当数学建模国赛遇上最短路径每年九月的全国大学生数学建模竞赛国赛对无数理工科学生来说都是一场硬仗。题目往往取材于现实中的复杂问题要求你在三天三夜内用数学模型和算法给出解决方案。2023年的赛题中涉及路径规划、网络优化的问题并不少见而Dijkstra算法作为求解最短路径问题的经典基石其重要性不言而喻。很多队伍拿到题目一看有“最短时间”、“最低成本”、“最优路线”这些字眼第一反应可能就是“上Dijkstra”。这个思路没错但想把Dijkstra用对、用好、用在刀刃上远不是调用一个库函数那么简单。我参加过也指导过多次数模竞赛亲眼见过不少队伍在这个“经典算法”上栽跟头。有的团队直接套用课本上的伪代码结果面对成千上万个节点时程序跑了一夜都没结果有的团队忽略了题目中“路径不能重复经过某点”的隐含约束导致模型失效更常见的是只算出了最短路径长度却对如何将结果清晰地可视化、如何有说服力地写入论文一筹莫展。这次我就以“使用Dijkstra算法求最短路径”这个核心任务为线索拆解在国赛高压环境下如何从理解问题、实现算法、到结果呈现的全流程实战经验。无论你是用Matlab、Python还是C这里的思路和避坑指南都是相通的。2. 核心需求解析国赛题中的“最短路径”到底在问什么国赛题目从来不会直白地说“请用Dijkstra算法计算最短路径”。它通常包裹在一个生动的场景里。比如可能是“灾后应急物资配送路线规划”要求你考虑道路损毁边权值变为无穷大和通行时间边权值为时间也可能是“通信网络骨干链路铺设”要求成本最低边权值为费用且需连接所有关键节点。因此我们的第一要务不是急着写代码而是抽象建模。2.1 从赛题描述到图模型抽象首先必须精准识别“节点”和“边”。节点可以是城市、路口、通信基站、物流中心边则是连接它们的道路、线路或运输关系。这一步极易出错。例如一个“中转枢纽”在题目中可能既是一个消耗资源的“点”也是一条具有处理能力的“边”需要根据问题决定其建模方式。其次定义“权值”。这是Dijkstra算法的输入核心。权值必须是非负的这符合现实多数场景距离、时间、成本不为负。但国赛题有时会暗藏玄机比如“节省的时间”可能作为负权值出现这时Dijkstra算法就直接失效了需要考虑Bellman-Ford或SPFA算法。所以读题时要像侦探一样确认权重的物理意义和数学符号。最后明确“源点”和“终点”。是单源最短路径一个起点到所有其他点还是固定点对之间的最短路径这决定了算法输出的结构。通常国赛要求的是后者但计算过程往往是前者。注意务必在论文的模型假设部分清晰地阐述你的图模型抽象过程。评阅老师会首先检查你的模型转换是否合理这是得分的基础。2.2 Dijkstra算法的适用性与局限性认知Dijkstra算法解决的是带权有向图或无向图的单源最短路径问题。它的核心思想是贪心算法通过不断选取当前未访问节点中距离源点最近的节点来逐步确定到所有节点的最短距离。在国赛中的应用优势非常明显算法经典易于实现和解释在采用优先队列优化后对于节点数在10^4~10^5级别的稀疏图效率很高。Matlab中也有类似的graph和shortestpath函数可以快速验证。但其局限性在国赛中更需警惕负权边绝对禁止。这是算法数学原理决定的。大规模稠密图当边数量接近节点数的平方时即使用堆优化复杂度O((nm)log n)也可能让你在时限内无法完成计算。这时需要考虑更高效的算法或启发式方法。动态变化如果题目中网络结构如道路封闭或边权如拥堵系数随时间变化标准的静态Dijkstra需要嵌入到时间迭代框架中或转而使用动态规划思想。理解这些你才能判断Dijkstra是不是本题的“银弹”或者是否需要将其作为更复杂模型中的一个子模块。3. 算法实现与优化从理论伪代码到竞赛级代码理解了问题接下来就是动手实现。虽然Matlab等工具内置了函数但在国赛中自己实现一个算法并展示出来往往能体现更高的模型掌控力和论文深度。3.1 基础实现邻接矩阵与邻接表的选择这是第一个性能分水岭。假设我们有一个n个节点、m条边的图。邻接矩阵用一个n×n的二维数组dist存储任意两点间的直接距离。无边则设为无穷大Inf自身到自身为0。% 假设有5个节点 n 5; adj_matrix inf(n, n); for i 1:n adj_matrix(i, i) 0; end % 添加边例如节点1到节点2权值为4 adj_matrix(1, 2) 4; adj_matrix(2, 1) 4; % 如果是无向图优点直观检查两点是否直接相连是O(1)操作。缺点空间复杂度O(n^2)对于稀疏图m远小于n^2极度浪费。在国赛中节点数上千时内存就可能告急。邻接表为每个节点维护一个列表存储其所有邻居节点及对应的边权。% 使用元胞数组存储邻接表 adj_list cell(n, 1); % 添加同样的边节点1到节点2权值4 adj_list{1} [adj_list{1}; 2, 4]; adj_list{2} [adj_list{2}; 1, 4]; % 无向图优点空间复杂度O(nm)完美适配稀疏图也是绝大多数实际网络社交网络、道路网的特点。缺点查询任意两点是否直接相连需要遍历列表效率稍低。国赛实战选择除非题目明确给出的是小规模完全图否则一律优先使用邻接表。这是处理大规模数据的基本素养。3.2 核心算法实现朴素法与堆优化朴素Dijkstra使用邻接矩阵 这是教科书版本复杂度O(n^2)。其步骤清晰适合在小规模问题中演示。初始化设置源点s的距离dist[s]0其他点dist[i]Inf。所有点未访问。循环n次在所有未访问节点中找到dist值最小的节点u标记u为已访问。松弛操作遍历u的所有邻居v。如果dist[u] w(u, v) dist[v]则更新dist[v] dist[u] w(u, v)。循环结束dist数组即为源点到各点的最短距离。这个算法的瓶颈在第2步“查找最小dist节点”需要遍历所有未访问节点是O(n)操作执行n次就是O(n^2)。堆优化Dijkstra使用邻接表 这是国赛乃至工程中的标配复杂度O((nm) log n)。核心是用一个最小堆优先队列来高效完成“查找最小dist节点”的操作。初始化dist数组同上。创建一个最小堆或优先队列将源点s及其距离0入堆。当堆不为空弹出堆顶元素当前距离源点最近的节点u。如果u已被访问跳过这是处理堆中冗余键的关键。否则标记u为已访问。松弛操作遍历u的所有邻居v。如果通过u可以缩短到v的距离则更新dist[v]并将(dist[v], v)这个新对加入堆中。在Matlab中没有内置的堆数据结构但我们可以用containers.Map模拟或者更高效地直接使用priorityqueue需要R2020b以上版本或使用File Exchange中的第三方实现。在Python中可以使用heapq模块在C中使用priority_queue。% 一个简化的Matlab思路使用矩阵操作非严格堆优化但适用于中等规模 function [dist, prev] dijkstra_heap(adj_list, s) n length(adj_list); dist inf(1, n); dist(s) 0; visited false(1, n); prev zeros(1, n); % 用于回溯路径 % 使用一个数组模拟每次用min找这其实还是O(n^2)查找仅作示意。 % 真正堆优化需要实现优先队列。 for i 1:n % 找到未访问节点中dist最小的 [minDist, u] min(dist .* ~visited visited * inf); if isinf(minDist), break; end % 剩余节点不可达 visited(u) true; % 遍历邻居 neighbors adj_list{u}; for j 1:size(neighbors, 1) v neighbors(j, 1); w neighbors(j, 2); if dist(u) w dist(v) dist(v) dist(u) w; prev(v) u; end end end end实操心得在国赛有限的时间内如果节点数超过500强烈建议你寻找或提前准备一个堆优化的Dijkstra实现。这能节省大量计算时间让你把精力放在模型分析和论文写作上。可以直接在论文附录中贴出优化后的核心代码这是加分项。3.3 路径回溯与输出算法计算出了最短距离但题目通常要求“给出具体路径”。这需要我们在算法过程中记录“前驱节点”。 在松弛操作if dist[u] w dist[v]成立时除了更新dist[v]还要记录prev[v] u表示到v的最短路径是从u过来的。计算结束后从终点t开始不断查找prev[t]直到回溯到源点s再逆序即可得到路径。function path get_path(prev, s, t) path []; if isinf(dist(t)) % 终点不可达 return; end current t; while current ~ s path [current, path]; current prev(current); end path [s, path]; end4. 在Matlab中的高效实现与技巧对于很多参赛队Matlab是首选工具因其强大的数学计算和可视化能力。这里重点讲Matlab环境下的实操。4.1 利用内置函数快速验证在建模初期快速验证想法的正确性至关重要。Matlab的graph和digraph对象以及相关的函数是神器。% 创建无向图 s [1 1 2 3 4]; % 边的起点 t [2 3 4 5 5]; % 边的终点 w [4 2 5 1 3]; % 边的权重 G graph(s, t, w); % 计算节点1到节点5的最短路径和距离 [path, dist] shortestpath(G, 1, 5); % path [1 3 5], dist 3 (21) % 计算节点1到所有节点的最短距离 dist_all distances(G, 1);优点代码极其简洁内置算法经过高度优化稳定可靠。非常适合用于小规模验证、对比自己算法结果的正确性或者作为最终模型的一个可靠组成部分。缺点作为“黑箱”在论文中直接调用并声称“我们使用了Dijkstra算法”会显得深度不足。更适合作为辅助工具。4.2 处理大规模数据稀疏矩阵表示法当节点数上万时邻接矩阵内存爆炸邻接表的元胞数组操作也可能较慢。Matlab的稀疏矩阵sparse是处理此类问题的绝佳选择。% 使用稀疏矩阵构建邻接矩阵 n 10000; s [...]; % 起点向量 t [...]; % 终点向量 w [...]; % 权值向量 % 构建对称稀疏矩阵无向图 A sparse([s, t], [t, s], [w, w], n, n); % 此时A(i,j)就是i到j的权值不存在则为0需要后续替换为Inf % 将0值无边替换为Inf A(A 0) Inf; for i 1:n A(i, i) 0; end使用稀疏矩阵后你可以用相对简洁的矩阵操作来实现朴素Dijkstra虽然复杂度仍是O(n^2)但内存占用大大减少对于万级别节点的中等规模问题在可接受时间内也能跑出结果。4.3 可视化呈现让结果一目了然国赛论文中一张清晰的可视化图能极大提升表现力。% 绘制网络图 p plot(G, EdgeLabel, G.Edges.Weight, LineWidth, 2, MarkerSize, 7); highlight(p, path, EdgeColor, r, LineWidth, 3); % 高亮最短路径 highlight(p, path, NodeColor, r, MarkerSize, 10); title(sprintf(最短路径: %s, 总距离: %.2f, num2str(path), dist));可以进一步优化用不同颜色或粗细表示边权大小用地图背景如果问题是地理相关的制作路径演变的动态图for循环配合highlight和pause展示Dijkstra算法的逐步搜索过程这能在模型阐述部分给人留下深刻印象。5. 国赛实战中的典型问题与调优策略在实际竞赛中你会遇到比课本例题复杂得多的情况。下面是一些常见挑战及应对策略。5.1 多目标与约束条件处理国赛题很少只求“最短”。常伴随“在预算B内”、“时间窗口限制”、“节点访问次数限制”等。此时单纯的Dijkstra不够用。策略状态扩展法将原图转化为“状态空间图”。例如除了节点编号u再增加一维状态如剩余预算b或当前时间t。新图中的每个节点是(u, b)。在新图上运行Dijkstra或其他最短路径算法边权根据状态转移定义。这本质上是动态规划与图搜索的结合。例如问题“在总成本不超过C的前提下找最短时间的路径”。我们可以定义状态(城市, 已花费成本)。从(起点, 0)开始如果从城市u到城市v有一条路耗时time花费cost那么对于状态(u, spent)可以转移到(v, spentcost)转移的“距离”就是time。在新图中运行Dijkstra最终答案就是所有(终点, spent)其中spent C中距离最小的那个。这种方法会显著增加节点数原节点数×状态数但对中等规模问题依然可行。在论文中需要清晰地阐述状态定义和图的构建方法。5.2 超大规模图的近似求解当节点数达到百万级即使堆优化的Dijkstra也力不从心。国赛题有时会提供这样的海量数据来考验选手的算法选型能力。策略启发式算法或分层规划A*搜索算法如果问题有明确的几何信息如城市经纬度可以设计一个到终点的直线距离作为启发函数h(v)在Dijkstra的优先队列排序依据f(v) g(v) h(v)g(v)是已知距离中使用。这能极大缩小搜索范围快速找到可行解。但需要保证h(v)是可采纳的不大于实际剩余距离。双向Dijkstra同时从起点和终点运行Dijkstra算法当两边的搜索区域相遇时停止。平均能减少一半的搜索空间。分层/分区将大地图按行政区划或网格划分。先在高层次路网如高速公路网上规划粗略路径再在涉及的每个区域内进行精细规划。这需要你根据题目数据特征设计分层结构。在论文中如果采用了近似算法必须讨论解的质量与精确解或下界的差距和效率的平衡并说明为什么该策略适用于本问题。5.3 算法正确性验证与鲁棒性测试你的模型和代码必须经得起推敲。构造简单测试用例用手算就能知道答案的小图3-5个节点测试你的代码确保基础功能正确。对比内置函数用Matlab的shortestpath在中小规模随机图上与你的算法结果对比验证正确性。压力测试生成不同规模如100, 1000, 5000节点的随机图测试算法运行时间绘制时间-规模曲线分析是否符合预期复杂度。这能体现你的科学素养。边界条件测试源点就是终点。存在孤立节点不可达。图中存在环。最大权值非常大的情况。随机种子在生成随机数据或进行随机抽样时固定随机数种子如rng(2023)确保结果可复现。这是学术严谨性的体现。6. 论文写作要点如何展示你的工作算法实现只是第一步如何写在论文里让评委看懂并认可才是关键。6.1 模型建立部分这部分要清晰地展示从实际问题到图论模型的转化过程。符号说明用表格列出所有使用的变量、符号及其含义。例如G(V,E)表示图w(i,j)表示边权d[i]表示最短距离。模型假设明确列出。例如“假设运输车辆速度恒定故边权代表通行时间”、“忽略交通拥堵的动态变化”、“假设所有道路信息已知且确定”。图模型构建用文字和示意图说明如何将题目中的实体抽象为节点和边如何定义权值。最好画一个简单的示例图。算法选择论证简要说明为什么选择Dijkstra算法例如权值为非负是单源最短路径问题。如果做了优化如堆优化在这里提一句。6.2 算法求解部分这是核心。算法步骤不要直接贴代码。用伪代码或流程图来描述算法过程。伪代码应简洁突出逻辑使用公认的格式。例如算法1: 堆优化的Dijkstra算法 输入: 图G的邻接表adj_list, 源点s 输出: 源点s到所有点的最短距离dist[], 前驱节点prev[] 1. 初始化: dist[] ← INF, dist[s] ← 0, prev[] ← -1 2. 创建最小优先队列Q并将(s, 0)入队 3. while Q非空: 4. (d_u, u) ← Q.pop() // 取出当前距离最小的节点 5. if d_u dist[u]: continue // 跳过陈旧记录 6. for each neighbor v of u with weight w: 7. new_dist ← dist[u] w 8. if new_dist dist[v]: 9. dist[v] ← new_dist 10. prev[v] ← u 11. Q.push((new_dist, v)) 12. return dist[], prev[]关键步骤解释对伪代码中的关键行特别是优化点如第5行跳过陈旧记录和路径记录第10行进行文字解释。复杂度分析简要分析算法的时间复杂度和空间复杂度。例如“使用二叉堆实现优先队列时间复杂度为O((nm) log n)空间复杂度为O(nm)其中n为节点数m为边数。”6.3 结果分析与可视化部分数据呈现将主要结果以表格形式列出。例如列出到各重要目标点的最短路径及其长度。可视化放入精心设计的网络图和最短路径高亮图见4.3。图注要详细说明图中各元素代表什么。分析讨论不要只说“我们得到了最短路径”。要分析结果这条路径为什么是最优的它避开了哪些高成本边路径是否符合直观如果存在多条长度相近的路径可以做一个敏感性分析讨论它们的优劣。模型检验简要说明你如何验证了结果的正确性如6.3节所述。模型评价与推广客观评价模型的优点高效、清晰和缺点对负权边无效、静态模型等。说明模型可以推广到哪些类似场景物流配送、网络路由等。7. 常见失误与避坑指南结合多年评审和参赛经验总结几个最容易丢分的点混淆有向图与无向图题目说“道路是双向的”就建无向图两条有向边说“单行线”或“上下游关系”就建有向图。仔细读题权值定义错误把“时间”当“距离”或者忽略了转换系数如速度。务必确认权值的单位与题目要求输出的单位一致。忽略“不可达”情况图中可能存在不连通的子图。你的算法必须能处理这种情况输出应为无穷大Inf或一个特殊标识并在论文中说明。路径回溯代码有bug这是实现细节上的高频错误。务必用多个例子测试get_path函数特别是当起点等于终点、路径只有一条边的情况。论文中只有代码没有描述切忌大段粘贴源代码。核心是伪代码和文字解释完整代码可以放在附录。滥用“Dijkstra”这个词如果题目中有负权边即使你没发现而你用了Dijkstra整个模型就错了。一定要先论证权值的非负性。缺乏对比分析如果问题规模不大可以对比一下朴素Dijkstra和堆优化Dijkstra的运行时间用数据展示优化的效果这会让论文更出彩。可视化过于简陋使用默认设置的plot图节点和边挤在一起看不清。一定要调整布局如layout(force)或layout(layered)、节点大小、颜色、标签让图清晰易读。最后记住数学建模竞赛的本质是“建模”算法只是工具。Dijkstra算法本身很经典但如何将它嵌入到解决实际问题的完整框架中如何根据题目条件进行适配和扩展如何清晰且有说服力地呈现你的整个思考过程和解决方案这才是区分优秀论文与普通论文的关键。把每一步“为什么这么做”都想清楚、写明白你的国赛答卷就一定不会差。