1. 项目概述从“图”开始理解复杂世界的连接如果你正在准备数学建模竞赛或者在工作中遇到了需要分析网络关系、优化路径、分配资源的问题那么“图论”绝对是你绕不开的一个核心工具。很多人一听到“图论”就觉得抽象、复杂联想到一堆点和线感觉离实际应用很远。但恰恰相反图论是描述“关系”最直观、最有力的数学语言。从社交网络的好友关系、互联网的网页链接到物流配送的最优路线、芯片设计的电路布局甚至是我们大脑神经元之间的连接都可以抽象成“图”来研究。这次我们就从数学建模的实战角度出发来聊聊图论的基础和应用。这不是一堂枯燥的理论课而是一次“工具箱”的整理。我们会聚焦于一个最经典、也最实用的问题最短路径。想象一下你要为外卖平台设计一个派送算法如何在错综复杂的城市道路网中为骑手找到从A点到B点的最快路线这本质上就是一个在图道路网中寻找最短路径的问题。而解决这个问题的“明星算法”之一就是Dijkstra算法。在数学建模中我们不仅要知道算法原理更要能把它“跑起来”得到可视化的结果。因此MATLAB将成为我们得力的计算与可视化工具。它强大的矩阵运算能力和丰富的绘图函数非常适合用来实现图论算法并展示结果。我们将从如何用邻接矩阵这个核心数据结构在MATLAB中表示一张图开始一步步实现Dijkstra算法并解决一个实际的路径规划问题。无论你是初次接触图论的建模新手还是想巩固基础、寻找快速实现方案的参赛者这篇内容都将提供一条清晰的实践路径。2. 图论基础与核心数据结构邻接矩阵在动手写代码之前我们必须先统一“语言”。图论中的“图”Graph不是指函数图像或者饼图而是由顶点Vertex或节点Node和连接顶点的边Edge组成的集合。边可以有权重Weight比如距离、时间、成本等这样的图称为加权图我们的最短路径问题就是在加权图中寻找权重和最小的路径。2.1 邻接矩阵图的“数学身份证”如何在计算机特别是在MATLAB中表示一张图最常用、最直观的方法就是邻接矩阵。它是一个方阵行和列都对应图中的顶点。矩阵中的元素A(i, j)表示从顶点i到顶点j的边的权重。这个概念听起来简单但细节决定成败。我们来看一个具体的城市交通网络例子。假设有5个地点顶点0-4它们之间的道路边及驾车时间权重单位分钟如下从0到1需要10分钟。从0到3需要30分钟。从1到2需要50分钟。从2到4需要10分钟。从3到2需要20分钟。从3到4需要60分钟。注意这是一个有向图即道路可能是单行线从0到1需要10分钟不代表从1到0也是10分钟可能无法通行。如果所有道路都是双行的那就是无向图其邻接矩阵是对称的。那么它的邻接矩阵A是怎样的呢矩阵构建逻辑首先我们创建一个5x5的矩阵并初始化为一个很大的数比如Inf代表无穷大表示所有顶点之间初始都没有直接连通的边。填充权重对于每一条有向边(i, j, weight)我们令A(i, j) weight。注意矩阵索引在MATLAB中默认从1开始但我们的顶点编号是0-4。为了更直观我们通常将顶点映射为1-5。这里为了和算法描述统一我们在思维上使用0-4实际代码中会做1处理。对角线元素顶点到自身的距离通常设为0即A(i, i) 0。根据以上规则我们得到邻接矩阵A这里展示从1开始索引的版本顶点1对应原顶点0顶点: 1 2 3 4 5 [ 0, 10, Inf, 30, Inf; % 从顶点1原0出发 Inf, 0, 50, Inf, Inf; % 从顶点2原1出发 Inf, Inf, 0, Inf, 10; % 从顶点3原2出发 Inf, Inf, 20, 0, 60; % 从顶点4原3出发 Inf, Inf, Inf, Inf, 0] % 从顶点5原4出发Inf表示两点间没有直接连接的边。注意这是最基础的表示法。对于无向图A(i, j)和A(j, i)应填入相同的权重。对于超大规模稀疏图比如社交网络数亿用户但每人只连接几百人用Inf填充的稠密矩阵会浪费大量内存此时会采用稀疏矩阵存储MATLAB中的sparse函数。但在数学建模中处理几百、几千个节点的网络用全矩阵表示通常更直观方便。2.2 在MATLAB中创建与可视化邻接矩阵理解了原理我们在MATLAB中动手创建它。% 定义顶点数量 n 5; % 初始化邻接矩阵用 Inf 表示不直接连通 A inf(n, n); % 设置对角线为0每个点到自己的距离为0 for i 1:n A(i, i) 0; end % 填入有向边的权重 (注意这里索引对应顶点1~5) A(1, 2) 10; % 0-1 A(1, 4) 30; % 0-3 A(2, 3) 50; % 1-2 A(3, 5) 10; % 2-4 A(4, 3) 20; % 3-2 A(4, 5) 60; % 3-4 % 显示邻接矩阵 disp(邻接矩阵 A:); disp(A);仅仅有矩阵还不够直观。我们可以用graph和plot函数将图可视化出来这能帮助我们更好地理解网络结构也是建模论文中展示模型的重要一环。% 将邻接矩阵转换为图对象 % 注意graph函数会忽略Inf只处理有限权重的边 G digraph(A); % 使用 digraph 创建有向图如果是无向图用 graph(A) % 绘制图形 figure; h plot(G, EdgeLabel, G.Edges.Weight, LineWidth, 2, MarkerSize, 7, NodeColor, r, ArrowSize, 12); title(城市交通网络有向图权重为时间/分钟); grid on; % 美化调整布局使图形更清晰 layout(h, force); % 使用力导向布局可能会让图形分布更均匀运行这段代码你会看到一个有向箭头标识的图形每条边上都标有时间权重。这一步至关重要它完成了从抽象数据到直观形象的转换让你能“看见”你要处理的问题网络。3. Dijkstra算法原理与手动推演有了图的表示接下来就是核心如何找到从一个起点到其他所有点的最短路径Dijkstra算法就是解决非负权重加权图中单源最短路径问题的经典贪心算法。它的核心思想是“步步为营”逐步确定从源点到其他各顶点的最短距离。3.1 算法步骤拆解我们以顶点1源点对应原顶点0为例目标是求出它到所有其他顶点的最短时间。算法维护两个关键集合已确定最短路径的顶点集合S初始为空。未确定最短路径的顶点集合U包含所有顶点。以及两个关键数组dist记录从源点到每个顶点的当前已知最短距离估计值。初始时dist[源点]0其他为Inf。prev记录到达每个顶点的最短路径上的前驱顶点用于最后回溯路径。算法步骤如下初始化将源点dist设为0其余为Inf。S为空U包含所有顶点。选择从U中选出dist值最小的顶点u第一次就是源点自己。这个dist[u]此时就是它的最终最短距离因为所有边权非负不可能通过其他未确定的点找到更短的路了。标记将顶点u从U移到S中。松弛操作对于u的每一个邻居顶点v即存在边u-v检查如果从源点先到u再从u到v这条路径的距离dist[u] A(u, v)是否小于当前记录的dist[v]。如果是则更新dist[v] dist[u] A(u, v)并记录prev[v] u。这个操作是算法的核心它通过新加入的“跳板”u尝试优化到其他点的距离估计。循环重复步骤2-4直到U为空即所有顶点的最短距离都已确定。3.2 手动推演过程让我们结合前面的邻接矩阵手动推演从顶点1出发的过程。初始化dist [0, Inf, Inf, Inf, Inf](对应顶点1-5)prev [nil, nil, nil, nil, nil]S {},U {1,2,3,4,5}第1轮从U中找dist最小的顶点顶点1 (dist0)。将顶点1加入S。S{1},U{2,3,4,5}。松弛顶点1的邻居查看邻接矩阵第1行顶点1有边到顶点2(10)和顶点4(30)。对顶点2dist[1]A(1,2)01010dist[2]Inf更新dist[2]10,prev[2]1。对顶点4dist[1]A(1,4)03030dist[4]Inf更新dist[4]30,prev[4]1。更新后dist [0, 10, Inf, 30, Inf]第2轮U中dist最小的顶点是顶点2 (dist10)。将顶点2加入S。S{1,2},U{3,4,5}。松弛顶点2的邻居查看第2行顶点2有边到顶点3(50)。对顶点3dist[2]A(2,3)105060dist[3]Inf更新dist[3]60,prev[3]2。更新后dist [0, 10, 60, 30, Inf]第3轮U中dist最小的顶点是顶点4 (dist30)。将顶点4加入S。S{1,2,4},U{3,5}。松弛顶点4的邻居查看第4行顶点4有边到顶点3(20)和顶点5(60)。对顶点3dist[4]A(4,3)302050dist[3]60更新dist[3]50,prev[3]4。关键发现了更短的路径 1-4-3时间50分钟优于之前的1-2-3的60分钟对顶点5dist[4]A(4,5)306090dist[5]Inf更新dist[5]90,prev[5]4。更新后dist [0, 10, 50, 30, 90]第4轮U中dist最小的顶点是顶点3 (dist50)。将顶点3加入S。S{1,2,3,4},U{5}。松弛顶点3的邻居查看第3行顶点3有边到顶点5(10)。对顶点5dist[3]A(3,5)501060dist[5]90更新dist[5]60,prev[5]3。再次优化路径变为1-4-3-5时间60分钟更新后dist [0, 10, 50, 30, 60]第5轮U中只剩顶点5 (dist60)。将其加入S。算法结束。最终结果dist [0, 10, 50, 30, 60]即从顶点1出发到各点的最短时间为到2点10分钟到3点50分钟到4点30分钟到5点60分钟。prev [nil, 1, 4, 1, 3]通过prev可以回溯路径。例如到顶点5prev[5]3-prev[3]4-prev[4]1所以路径是 1-4-3-5。这个推演过程清晰地展示了Dijkstra算法如何像波浪一样从源点层层向外扩展逐步确定所有点的最短距离。理解这个过程是写出正确代码的基础。4. MATLAB实现Dijkstra算法理论明白了现在用MATLAB把它实现出来。我们将编写一个通用的函数dijkstra。4.1 函数设计与代码实现我们的函数需要输入邻接矩阵adjMatrix和起点startNode输出最短距离数组dist和前驱节点数组prev。function [dist, prev] dijkstra(adjMatrix, startNode) % DIJKSTRA 使用Dijkstra算法计算单源最短路径 % 输入 % adjMatrix - n x n 的邻接矩阵adjMatrix(i,j) 是从i到j的边权无连接则为Inf % startNode - 起始顶点的索引从1开始 % 输出 % dist - 1 x n 向量dist(i) 是从 startNode 到顶点 i 的最短距离 % prev - 1 x n 向量prev(i) 是最短路径上顶点 i 的前驱顶点用于路径回溯 n size(adjMatrix, 1); % 顶点数量 dist inf(1, n); % 初始化距离为无穷大 prev zeros(1, n); % 初始化前驱为0 visited false(1, n); % 标记顶点是否已确定最短路径即集合S dist(startNode) 0; % 起始点到自身的距离为0 for i 1:n % 步骤1: 在未访问节点中找到距离最小的节点 u minDist inf; u -1; for v 1:n if ~visited(v) dist(v) minDist minDist dist(v); u v; end end % 如果所有未访问节点距离都是无穷大说明剩下的节点不可达提前结束 if u -1 break; end visited(u) true; % 将节点u标记为已访问 % 步骤2: 松弛操作更新u的所有邻居的距离 for v 1:n % 如果存在从 u 到 v 的边 if adjMatrix(u, v) inf % 计算通过u到v的潜在新距离 alt dist(u) adjMatrix(u, v); % 如果新距离更短则更新 if alt dist(v) dist(v) alt; prev(v) u; end end end end end4.2 代码解析与关键点这段代码严格遵循了算法步骤但有几点需要特别关注visited数组它等价于算法描述中的集合S已确定和U未确定。visited(v)true表示顶点v在S中。寻找最小dist的循环这是算法效率的关键。我们使用了一个简单的线性扫描for v 1:n。这在顶点数n不大时比如几百个完全没问题。但如果n很大上万这个O(n)的查找会成为瓶颈此时应该使用**优先队列最小堆**来优化可以将查找最小值的复杂度降到O(log n)。在数学建模中根据问题规模选择实现方式很重要。提前终止条件if u -1这个判断很实用。当图不是全连通时有些顶点从起点无法到达其dist值保持Inf。这个判断可以避免无谓的循环。松弛操作if adjMatrix(u, v) inf判断边是否存在。alt dist(v)是松弛的核心判断逻辑。4.3 调用函数并验证结果现在我们用之前定义的邻接矩阵A和起点1来测试我们的函数。% 使用前面定义的邻接矩阵 A start 1; [shortestDistances, predecessors] dijkstra(A, start); % 显示结果 fprintf(从顶点 %d 出发到各顶点的最短距离\n, start); for i 1:length(shortestDistances) fprintf( 到顶点 %d: , i); if isinf(shortestDistances(i)) fprintf(不可达\n); else fprintf(%d 分钟\n, shortestDistances(i)); end end fprintf(\n前驱节点数组用于路径回溯\n); disp(predecessors);运行后你应该会看到shortestDistances [0, 10, 50, 30, 60]predecessors [0, 1, 4, 1, 3]。这与我们手动推演的结果完全一致4.4 路径回溯函数只有距离还不够我们通常需要知道具体的路径。根据prev数组我们可以写一个简单的回溯函数。function path getPath(prev, startNode, targetNode) % GETPATH 根据前驱数组prev回溯最短路径 % 输入 % prev - dijkstra函数输出的前驱数组 % startNode - 起始顶点 % targetNode - 目标顶点 % 输出 % path - 从startNode到targetNode的最短路径顶点序列 if prev(targetNode) 0 targetNode ~ startNode path []; % 不可达 return; end path []; u targetNode; while u ~ 0 path [u, path]; % 将当前节点添加到路径开头 u prev(u); % 移动到前驱节点 end % 确保路径起点正确当起点就是终点时 if path(1) ~ startNode path [startNode, path]; end end测试路径回溯target 5; pathSeq getPath(predecessors, start, target); if isempty(pathSeq) fprintf(从顶点 %d 到顶点 %d 没有路径\n, start, target); else fprintf(从顶点 %d 到顶点 %d 的最短路径为\n, start, target); fprintf( %s\n, strjoin(cellstr(num2str(pathSeq)), - )); fprintf(总距离%d 分钟\n, shortestDistances(target)); end输出应该是从顶点 1 到顶点 5 的最短路径为 1 - 4 - 3 - 5总距离60分钟。5. 可视化展示与结果分析“一图胜千言”。将算法计算出的最短路径在图上高亮显示能让你的建模报告增色不少。MATLAB的绘图功能可以轻松实现这一点。% 假设我们已经计算得到从起点1到终点5的路径 pathSeq [1, 4, 3, 5] % 以及整个图对象 G figure; p plot(G, EdgeLabel, G.Edges.Weight, LineWidth, 1.5, MarkerSize, 8, NodeColor, k); title(sprintf(从顶点%d到顶点%d的最短路径可视化, start, target)); grid on; highlight(p, start, NodeColor, g, MarkerSize, 10); % 高亮起点为绿色 highlight(p, target, NodeColor, r, MarkerSize, 10); % 高亮终点为红色 % 高亮最短路径上的边 if length(pathSeq) 2 for i 1:length(pathSeq)-1 highlight(p, pathSeq(i), pathSeq(i1), EdgeColor, b, LineWidth, 3); end end % 也可以高亮路径上的节点 highlight(p, pathSeq, NodeColor, c);在这张图中绿色起点红色终点蓝色的粗线就是Dijkstra算法为我们找到的最优路径。你可以清晰地看到算法没有选择看似更直接的 1-4-590分钟而是选择了 1-4-3-560分钟因为中间经过顶点3的那段边权重10非常“便宜”从而优化了总时间。5.1 结果分析与建模意义通过这个简单的例子我们可以看到Dijkstra算法在路径规划中的强大能力。在数学建模中这个模型可以轻松扩展到更多场景交通物流顶点是仓库、配送站或城市边权重是距离、时间或运费算法用于规划最优运输路线。网络路由顶点是路由器边权重是延迟或丢包率算法用于数据包转发。社交网络顶点是人边是关系亲密度算法可以用于寻找关系最紧密的路径虽然这里权重可能表示“距离”亲密度高则距离短。游戏地图顶点是地图格子边权重是移动成本平地、沼泽、山地成本不同用于NPC寻路。关键点Dijkstra算法要求所有权重为非负值。如果图中存在负权边比如某些道路有“时间奖励”算法可能失效此时需要使用能处理负权重的Bellman-Ford算法。6. 性能优化、常见问题与扩展思考我们实现的基础版本Dijkstra算法复杂度约为 O(n²)因为外层循环n次内层每次都要线性扫描n个节点找最小值。对于大规模图这显然不够高效。6.1 使用优先队列优化优化的核心在于将“查找未访问节点中dist最小的节点”这一操作加速。我们可以使用最小堆Min-Heap数据结构。MATLAB没有内置的堆但我们可以用containers.Map配合自定义比较逻辑模拟或者更简单地使用priorityqueue需要安装第三方工具如MATLAB File Exchange上的相关提交。这里给出一个使用min函数但优化了扫描范围的思路以及概念性的伪代码。优化思路我们不再每次都扫描所有节点而是维护一个“未确定节点距离列表”的优先队列。每次从队列中弹出距离最小的节点u然后对其邻居进行松弛。如果松弛成功更新了某个邻居v的距离就将v的新距离插入或更新到优先队列中。% 伪代码/概念性描述非直接可运行代码 function [dist, prev] dijkstra_heap(adjMatrix, startNode) n size(adjMatrix, 1); dist inf(1, n); prev zeros(1, n); dist(startNode) 0; % 创建一个优先队列最小堆元素为 [距离, 顶点] pq PriorityQueue(); % 假设有此数据结构 pq.insert([0, startNode]); while ~pq.isEmpty() [currentDist, u] pq.extractMin(); % 取出当前距离最小的顶点 % 如果取出的距离大于当前记录的距离说明是过时的队列项跳过 if currentDist dist(u) continue; end % 遍历邻居 for v 1:n if adjMatrix(u, v) inf alt dist(u) adjMatrix(u, v); if alt dist(v) dist(v) alt; prev(v) u; pq.insert([alt, v]); % 将更新后的节点加入队列 end end end end end使用优先队列后算法复杂度可降至 O((VE) log V)其中V是顶点数E是边数。对于稀疏图E远小于V²提升巨大。6.2 常见问题与调试技巧在实现和使用Dijkstra算法时你可能会遇到以下问题结果全是Inf或部分Inf检查邻接矩阵初始化确保没有直接连通的边被正确赋值而不是全部是Inf。检查对角线是否设为0。检查图的连通性你的起点可能在一个孤立的子图里无法到达其他节点。建模时要考虑这种情况并在结果中说明。检查算法中的松弛条件确保if adjMatrix(u, v) inf和if alt dist(v)判断正确。路径回溯错误或进入死循环检查prev数组初始化prev应初始化为0或-1等特殊值表示无前驱。在回溯函数中循环终止条件while u ~ 0要与之匹配。检查prev更新逻辑确保只有在距离被更新时才更新prev(v) u。在回溯函数中加入防错机制比如设置最大回溯步数防止因prev数组错误如形成环导致的无限循环。算法运行速度慢评估问题规模对于节点数超过1000的稠密图O(n²)的算法会变慢。考虑使用上述优先队列优化。使用稀疏矩阵如果图是稀疏的边数远小于n²用sparse矩阵存储邻接矩阵可以节省大量内存和计算时间。sparse矩阵在进行find操作找邻居时效率很高。% 将稠密矩阵A转换为稀疏矩阵S S sparse(A); % 在算法中遍历邻居可以这样写 [neighbors, ~, weights] find(S(u, :)); % 找到顶点u的所有出边邻居及权重 for idx 1:length(neighbors) v neighbors(idx); w weights(idx); % ... 松弛操作 ... end权重为负值导致错误理解算法前提Dijkstra算法不能处理负权边。如果图中可能存在负权例如某些建模场景中的“收益”或“成本节省”需要在数据预处理阶段进行检查或者换用Bellman-Ford算法。6.3 扩展思考从最短路径到建模应用掌握了单源最短路径我们可以将其作为模块解决更复杂的建模问题多源最短路径如果需要计算所有顶点两两之间的最短路径例如计算一个区域所有物流中心之间的最短距离矩阵可以对每个顶点作为起点都运行一次Dijkstra算法。对于稠密图Floyd-Warshall算法动态规划在编码上可能更简洁。K最短路径有时最优路径可能因为拥堵、事故等原因不可用需要备选方案。Yens算法等可以用于寻找前K条最短路径。带约束的最短路径在路径规划中可能还有时间窗、载重限制、风险成本等约束。这通常需要将问题转化为网络流问题或使用启发式算法如遗传算法、模拟退火来求解。动态图的最短路径如果边的权重随时间变化如交通拥堵这就是时变网络下的最短路径问题算法会更加复杂。在数学建模竞赛中清晰地定义顶点和边合理设置权重是成功应用图论的关键。例如在“节能减排”背景下规划车辆路径权重可以综合距离油耗、路况时间、收费成本甚至碳排放量通过赋予不同因子权重将其整合为一个综合成本。Dijkstra算法求出的就是综合成本最低的路径。最后我个人在多次建模中的体会是图论是一个极其强大的“建模思维”。很多时候成功的第一步不是急于套算法而是能否将实际问题准确地抽象为“图”。一旦完成了这一步你就拥有了一个庞大的算法武器库最短路径、最小生成树、最大流、拓扑排序等来解决问题。而MATLAB作为实现和验证算法的平台其矩阵化操作和可视化能力能让你的想法快速得到验证和呈现。从这个小项目开始尝试用图的视角去观察和分析你身边的问题你会发现一片新的天地。