1. 从“七桥问题”到知识图谱图论为何是建模的基石如果你正在接触数学建模尤其是涉及到路径规划、网络分析、资源分配或者社交关系这类问题时你大概率绕不开一个词图论。它听起来有点抽象像是纯数学领域的高深学问但事实上它可能是你工具箱里最接地气、最“能打”的实用工具之一。想象一下你要为外卖平台规划最优送餐路线要分析社交媒体上的信息传播路径甚至要理解城市地铁网络的换乘效率这些问题的底层结构都是一个由“点”和“边”构成的“图”。我最初接触图论也是在一次数学建模竞赛中面对一个复杂的交通流优化题目当我把十字路口抽象为节点、道路抽象为边、通行时间作为边的权重时整个混沌的问题瞬间变得清晰可解。那种“降维打击”的感觉至今记忆犹新。今天我们就来深入聊聊图论在数学建模中的核心地位以及如何用最经典的Dijkstra算法和MATLAB这把“瑞士军刀”来解决最短路径这个最基础也最经典的问题。无论你是刚入门的新手还是想巩固基础的进阶者这篇文章都将带你绕过理论深坑直击实战核心。图论的故事可以从18世纪的哥尼斯堡七桥问题讲起但它的现代价值远超于此。在数学建模中图论提供了一种强大的语言和框架将纷繁复杂的现实系统如交通网、通信网络、社交关系、生物神经网络抽象为简单的数学模型。这种抽象能力是建模的第一步也是关键一步。一个“图”由两部分组成顶点或节点Vertex和边Edge。顶点代表系统中的实体如城市、人物、服务器边代表实体之间的关系或连接如公路、友谊、数据链路。如果边有方向如单行道、关注关系就是有向图如果边没有方向如友谊、合作道路就是无向图。如果边上还附带了数量信息如距离、成本、流量那就是带权图。你看短短几句话我们就定义了一套可以描述万千世界的语法。在数学建模竞赛或实际项目中图论的应用场景极其广泛。除了最短路径还包括最小生成树如电网布局、通信网络建设成本最低、网络流如物流运输、管道输油的最大流量、匹配问题如求职者与岗位的配对、着色问题如考试时间表安排避免课程冲突以及当下热门的知识图谱构建。知识图谱本质上就是一个巨大的语义网络图其中的节点是实体或概念边是它们之间的关系而它的存储和计算基础正是我们马上要讲的邻接矩阵。所以掌握图论就等于拿到了一把开启复杂系统分析大门的钥匙。2. 图的计算机表示邻接矩阵与关联矩阵在动手写代码之前我们必须解决一个根本问题如何让计算机“理解”我们脑海中的那个图人眼一看就能明白的点线关系计算机需要一种精确、无歧义的数据结构来存储。这里最常用、最核心的两种表示方法就是邻接矩阵和关联矩阵。理解它们的优劣和适用场景是高效实现图算法的前提。2.1 邻接矩阵稠密网络的“全景地图”邻接矩阵是表示图的最直观方式之一。对于一个有n个顶点的图我们用一个n×n的方阵A来表示。矩阵的行和列都对应着图的顶点。矩阵元素A(i, j)的值定义了从顶点i到顶点j的边的情况。对于无权图如果顶点i到顶点j有一条边则A(i, j) 1否则为0。对于无向图由于边没有方向从i到j和从j到i是同一条边因此邻接矩阵是对称矩阵即A(i, j) A(j, i)。对于带权图A(i, j)的值就是边(i, j)的权重如距离、成本。如果两点之间没有直接相连的边在最短路径问题中我们通常用一个非常大的数如Inf无穷大来表示意味着“不可直接到达”。我们来看一个具体的例子。假设有一个4个城市A, B, C, D的公路网是无向带权图。城市间的距离如下A-B: 5, A-C: 8, B-C: 2, B-D: 7, C-D: 4。没有直接连接的距离视为无穷大。那么它的邻接矩阵用MATLAB表示将是% 顶点顺序: A1, B2, C3, D4 n 4; Inf 1e100; % 用一个极大数代表无穷大MATLAB中1e100是有效的表示 adj_matrix zeros(n, n); adj_matrix(1,2)5; adj_matrix(2,1)5; adj_matrix(1,3)8; adj_matrix(3,1)8; adj_matrix(2,3)2; adj_matrix(3,2)2; adj_matrix(2,4)7; adj_matrix(4,2)7; adj_matrix(3,4)4; adj_matrix(4,3)4; % 将对角线以外的零元素设为Inf表示无直接连接 for i1:n for j1:n if i~j adj_matrix(i,j)0 adj_matrix(i,j) Inf; end end end disp(adj_matrix);输出结果会是一个对称矩阵对角线为0自己到自己的距离为0有直接连接的位置是对应的权重其他位置是Inf。邻接矩阵的优势在于直观清晰查看任意两个顶点间是否有边、边的权重是多少只需要O(1)的时间直接索引即可。便于某些计算图的一些性质可以通过矩阵运算来研究例如邻接矩阵的k次幂其(i, j)元素的值表示从顶点i到顶点j长度为k的路径的数目对于无权图。但其劣势也很明显空间消耗大需要O(n²)的存储空间。对于顶点数很多例如上万个但边很稀疏每个顶点只和少数几个其他顶点相连的图比如社交网络、网页链接图这个矩阵将充满大量的0或Inf造成巨大的空间浪费。遍历邻居效率低要找出一个顶点的所有邻居需要扫描矩阵对应的一整行时间复杂度是O(n)即使这个顶点只有两三个邻居。实操心得在MATLAB中处理大型稀疏图时直接使用全矩阵full matrix存储邻接矩阵很可能会耗尽内存。这时sparse矩阵是你的救星。你可以用三个向量分别存储边的起点、终点和权重然后用sparse(i, j, w, n, n)来创建稀疏矩阵。这能极大节省内存和计算时间。例如sparse([1 1 2 2 3], [2 3 3 4 4], [5 8 2 7 4], 4, 4)可以高效地创建上述例子的矩阵0元素不会被存储。2.2 关联矩阵侧重边与顶点关系的“清单”关联矩阵是另一种表示方法它更侧重于“边”。对于一个有n个顶点、m条边的图关联矩阵B是一个n×m的矩阵。矩阵的行对应顶点列对应边。元素B(i, k)表示顶点i与边k的关联关系。对于无向图如果边k连接了顶点i则B(i, k)1否则为0。因此每条边对应的列会有两个1。对于有向图通常规定如果边k从顶点i出发则B(i, k) -1如果边k指向顶点j则B(j, k) 1不关联的为0。关联矩阵在理论研究和某些特定问题如电路网络分析、网络流问题的单纯形法中很有用因为它能清晰地表达基尔霍夫电流定律等约束。但在大多数算法竞赛和工程实现中尤其是最短路径、深度优先搜索等算法邻接矩阵或其变体邻接表更为常用因为算法更关心顶点间的直接连接关系。选择哪一种如果你的图非常稠密边数接近n²或者需要频繁进行任意两点间边的查询或者想利用矩阵运算那么邻接矩阵是合适的选择。如果你的图非常稀疏或者算法需要频繁遍历每个顶点的所有邻居如BFS、DFS、Dijkstra那么邻接表Adjacency List是更优的选择。邻接表为每个顶点维护一个链表链表中存储其所有邻居顶点及边的权重。它在空间上仅需O(nm)遍历邻居的时间复杂度与邻居数量成正比效率极高。在MATLAB中我们可以用元胞数组cell array来模拟邻接表adj_list{i}存储一个列表包含顶点i的所有邻居和权重。在接下来的Dijkstra算法实现中为了兼顾教学的清晰性和对稠密/稀疏图的适应性我们将主要使用邻接矩阵但会指出如何适配邻接表。3. Dijkstra算法全解析不只是“最短路径”当提到最短路径几乎所有人第一个想到的就是Dijkstra算法。它由荷兰计算机科学家艾兹赫尔·戴克斯特拉于1956年提出解决的是带权有向图或无向图且所有权重均为非负值中从一个单一源点到所有其他顶点的最短路径问题。它的核心思想是一种“贪心”策略每次从未确定最短路径的顶点集合中选取一个距离源点最近的顶点认为这个距离就是它的最终最短距离然后通过这个顶点去“松弛”更新其邻居顶点的距离估计。3.1 算法步骤与手动模拟让我们抛开复杂的数学符号用人话和例子走一遍流程。假设我们要求下图中从顶点A到其他所有顶点的最短距离。(A) 5/ \8 / \ (B)--2--(C) \7 4/ \ / (D)图一个简单的带权无向图边权重如上所示我们维护两个集合S已确定最短路径的顶点集合和U未确定的顶点集合。以及一个数组dist记录从源点A到每个顶点的当前最短距离估计。一个数组prev记录到达该顶点的最短路径上的前驱顶点用于最后回溯路径。初始化S {}U {A, B, C, D}dist[A]0,dist[B]Inf,dist[C]Inf,dist[D]Infprev全部初始化为空或-1迭代过程第一轮从U中找出dist最小的顶点是Adist0。将A加入S并从U中移除。然后检查A的所有邻居B, C对于Bdist[A] weight(A,B) 05 5小于当前的dist[B]Inf所以更新dist[B]5,prev[B]A。对于C088 Inf更新dist[C]8,prev[C]A。 此时状态S{A},U{B,C,D},dist[0,5,8,Inf]第二轮U中dist最小的是Bdist5。将B加入S检查B的邻居A, C, DA已在S中跳过。对于Cdist[B]weight(B,C)527小于当前的dist[C]8所以更新dist[C]7,prev[C]B。这是一个关键更新我们发现经过B到C比直接从A到C更短。对于D5712 Inf更新dist[D]12,prev[D]B。 状态S{A,B},U{C,D},dist[0,5,7,12]第三轮U中dist最小的是Cdist7。将C加入S检查C的邻居A, B, DA, B已在S中跳过。对于Ddist[C]weight(C,D)7411小于当前的dist[D]12所以更新dist[D]11,prev[D]C。 状态S{A,B,C},U{D},dist[0,5,7,11]第四轮U中只剩Ddist11。将D加入S。D没有未处理的邻居或邻居都在S中算法结束。最终结果从A到各点的最短距离B:5, C:7, D:11。路径回溯通过prev到Dprev[D]C-prev[C]B-prev[B]A所以路径是 A-B-C-D。到CA-B-C。到BA-B。这个手动模拟的过程清晰地展示了Dijkstra算法“步步为营逐步确认”的特点。它之所以正确依赖于一个关键前提所有边的权重非负。因为一旦有负权边已经加入集合S的顶点其“最短距离”可能因为后续发现的负权边而被推翻从而导致算法失效。对于含负权边的图需要使用Bellman-Ford算法。3.2 时间复杂度与优化朴素实现 vs 优先队列上述描述的是最朴素的Dijkstra算法实现。在每一轮中我们需要从U集合中找出dist最小的顶点。如果U用普通数组或链表存储每次查找最小值需要遍历整个U复杂度为O(n)。总共需要进行n轮这样的操作所以查找最小值的总代价是O(n²)。此外每轮还需要遍历当前顶点的所有邻居来更新dist对于邻接矩阵遍历所有邻居需要O(n)因为要扫描一行总更新代价也是O(n²)。因此基于邻接矩阵的朴素Dijkstra算法时间复杂度是O(n²)。这对于顶点数上千的图效率就开始捉襟见肘了。优化的核心在于如何高效地从U中取出dist最小的顶点。这里就要用到优先队列通常用最小堆实现。我们可以将U中的顶点及其当前dist值放入一个最小堆中堆顶永远是dist最小的顶点。查找最小值直接从堆顶取出时间复杂度O(1)。更新dist值当某个顶点的dist被更新后我们需要在堆中调整该顶点的位置“降低键值”操作时间复杂度为O(log n)。在稀疏图中边数m远小于n²每个顶点只会被插入堆中一次被取出一次每条边只会引起一次可能的“降低键值”操作。因此使用邻接表和优先队列优化的Dijkstra算法其时间复杂度可以降为O((nm) log n)对于稀疏图m ~ n这近似于O(n log n)效率提升巨大。在MATLAB中虽然没有内置的堆数据结构但我们可以通过一些技巧来模拟或者使用min函数配合逻辑索引来实现近似效果但性能上对于大规模图可能不如专门用C等语言实现的优先队列。对于教学和中小规模问题朴素的O(n²)实现完全够用且代码更清晰。4. 在MATLAB中手搓Dijkstra从脚本到函数理论懂了手动模拟也会了接下来就是实战环节如何在MATLAB中实现Dijkstra算法我将提供一个清晰、健壮、带详细注释的代码实现并封装成一个可重用的函数。这个实现基于邻接矩阵并包含了路径回溯功能。4.1 核心函数实现我们将实现一个函数[dist, path] myDijkstra(adj_matrix, start_node)。输入adj_matrix: n×n的邻接矩阵。adj_matrix(i,j)表示从顶点i到j的边的权重。如果i和j之间没有直接边应设为Inf。对角线元素应为0。start_node: 起始顶点的编号1到n之间的整数。输出dist: 一个1×n的向量dist(i)是从start_node到顶点i的最短距离。path: 一个元胞数组path{i}是一个向量表示从start_node到顶点i的最短路径经过的顶点序列包含起点和终点。如果不可达则为空数组[]。function [dist, path] myDijkstra(adj_matrix, start_node) % MYDIJKSTRA 使用Dijkstra算法计算单源最短路径 % 输入 % adj_matrix - n x n 邻接矩阵权重非负无直接连接为Inf自身为0 % start_node - 起始顶点编号 (1-based index) % 输出 % dist - 1 x n 向量从起点到各点的最短距离 % path - 1 x n 元胞数组每个元胞包含从起点到该点的路径顶点序列 n size(adj_matrix, 1); % 顶点数量 if start_node 1 || start_node n error(起始顶点编号超出范围。); end % 初始化 dist inf(1, n); % 距离初始化为无穷大 prev zeros(1, n); % 前驱顶点0表示无前驱起点或未访问 visited false(1, n); % 标记顶点是否已确定最短路径 dist(start_node) 0; % 起点到自身的距离为0 % 主循环需要确定n个顶点的最短路径 for i 1:n % 步骤1从未访问顶点中选取当前距离最小的顶点u % 找出所有未访问顶点中dist最小的索引 unvisited_dist dist; unvisited_dist(visited) inf; % 将已访问顶点的距离设为inf确保不会被选到 [min_dist, u] min(unvisited_dist); % 如果最小距离是inf说明剩下的顶点都不可达可以提前结束 if isinf(min_dist) break; end visited(u) true; % 标记顶点u为已访问已确定最短路径 % 步骤2松弛操作 - 更新u的所有邻居的距离 % 遍历所有顶点v for v 1:n % 如果v未访问且u到v有边权重不是inf if ~visited(v) adj_matrix(u, v) inf % 计算通过u到v的潜在新距离 new_dist dist(u) adj_matrix(u, v); % 如果新距离更短则更新 if new_dist dist(v) dist(v) new_dist; prev(v) u; % 记录前驱 end end end end % 根据prev数组回溯构造路径 path cell(1, n); for target 1:n if isinf(dist(target)) % 不可达 path{target} []; else % 从终点反向回溯到起点 seq []; t target; while t ~ 0 seq [t, seq]; % 将当前顶点加入序列头部 t prev(t); % 移动到前驱顶点 end path{target} seq; end end end4.2 代码详解与避坑指南这段代码严格遵循了Dijkstra算法的步骤但有几个关键细节和潜在的“坑”需要特别注意Inf的使用与判断MATLAB中Inf代表无穷大。在初始化距离和判断无边时我们都用了Inf。在比较adj_matrix(u, v) inf时是安全的。但注意如果图中真的存在权重为Inf的边理论上不应该这个判断会失效。通常我们确保无直接连接的边就是Inf。选取最小dist顶点这是朴素实现的核心。我们通过一个技巧来实现unvisited_dist dist; unvisited_dist(visited) inf;。我们将已访问顶点的dist临时设为Inf这样min函数就会自动在未访问顶点中寻找最小值。这比用循环判断visited状态更简洁高效。提前终止条件if isinf(min_dist) break;这一行是重要的优化。当未访问顶点中的最小距离都是Inf时说明剩下的顶点从起点都不可达没有必要继续循环。对于连通图这个条件可能永远不会触发但对于非连通图它能节省大量不必要的计算。路径回溯prev数组记录了每个顶点的“前驱”。回溯时我们从终点开始不断查找前驱直到找到起点前驱为0。注意构建路径序列时我们使用seq [t, seq];将当前顶点插入序列头部以保证最终路径是从起点到终点的正确顺序。如果使用seq [seq, t];追加到尾部得到的就是逆序路径。关于索引MATLAB默认使用1-based索引数组下标从1开始。我们的顶点编号也是从1到n。这与C、Python等语言的0-based索引习惯不同在将算法从其他语言移植到MATLAB时要特别注意。实操心得与常见错误负权边这是Dijkstra算法的“死穴”。如果你的图中有负权边比如某些场景下的“收益”可以视为负成本上述代码会给出错误结果。务必在调用前检查邻接矩阵。自环与重边邻接矩阵通常只保留最小权重边如果是求最短路径。如果输入矩阵包含自环ij且权重非0算法可能出错因为自己到自己的距离应该永远是0。我们的代码中adj_matrix(u,v)当uv时如果权重不为0会被错误地用于松弛。安全的做法是在初始化时确保对角线为0或者在松弛判断中增加u ~ v的条件。大规模图性能对于n很大的图比如上万节点这个O(n²)的循环会非常慢。在MATLAB中向量化操作比循环快。一个优化思路是在松弛步骤可以尝试用矩阵操作替代内层循环但逻辑会复杂很多。对于真正的性能需求考虑使用MATLAB内置的graph和shortestpath函数基于更高效的算法或者用其他语言实现。路径存储对于顶点数极多的图为每个目标点存储完整路径可能消耗大量内存。如果只关心距离不关心具体路径可以不计算path。如果关心路径但内存紧张可以只输出prev数组需要时再按需回溯。4.3 实战测试验证我们的算法让我们用前面那个4个城市的例子来测试一下我们的函数。%% 测试用例四个城市的最短路径 % 构建邻接矩阵 n 4; adj_mat inf(n); % 初始化为全Inf adj_mat(1,2)5; adj_mat(2,1)5; adj_mat(1,3)8; adj_mat(3,1)8; adj_mat(2,3)2; adj_mat(3,2)2; adj_mat(2,4)7; adj_mat(4,2)7; adj_mat(3,4)4; adj_mat(4,3)4; for i1:n adj_mat(i,i) 0; % 对角线设为0 end start 1; % 从城市A顶点1出发 [distances, paths] myDijkstra(adj_mat, start); fprintf(从顶点 %d 出发到各顶点的最短距离和路径\n, start); for i 1:n fprintf( 到顶点 %d: 距离 %5.2f, 路径 , i, distances(i)); if isempty(paths{i}) fprintf(不可达\n); else fprintf(%s\n, num2str(paths{i})); end end运行这段代码你应该会看到如下输出从顶点 1 出发到各顶点的最短距离和路径 到顶点 1: 距离 0.00, 路径 1 到顶点 2: 距离 5.00, 路径 1 2 到顶点 3: 距离 7.00, 路径 1 2 3 到顶点 4: 距离 11.00, 路径 1 2 3 4这与我们手动模拟的结果完全一致证明算法实现正确。5. 超越基础MATLAB内置函数与实战扩展自己动手实现算法是理解其精髓的最佳途径。但在实际建模或工程中我们更倾向于使用成熟、高效、经过充分测试的工具。MATLAB早就为我们提供了强大的图论工具箱。了解并善用这些内置工具能让我们事半功倍。5.1 使用graph对象与shortestpath函数从MATLAB R2015b开始引入了面向对象的图论工具。创建图、计算最短路径变得异常简单。%% 使用MATLAB内置函数解决同一问题 % 方法1使用边列表创建无向图 s [1 1 2 2 3]; % 源顶点列表 t [2 3 3 4 4]; % 目标顶点列表 w [5 8 2 7 4]; % 权重列表 G graph(s, t, w); % 创建无向图 % 计算从节点1到所有节点的最短路径距离和路径 [dist_mat, path_mat] shortestpath(G, 1, all); % ‘all’表示计算到所有节点 fprintf(\n--- 使用MATLAB内置graph对象 ---\n); for i 1:numnodes(G) fprintf( 到节点 %d: 距离 %5.2f, 路径 , i, dist_mat(i)); fprintf(%s\n, num2str(path_mat{i})); end % 方法2直接从邻接矩阵创建图 % 注意graph(adj_mat)会将adj_mat视为有向图的邻接矩阵。 % 对于无向图我们的adj_mat是对称的所以可以直接用。 G2 graph(adj_mat); % adj_mat是前面定义的矩阵对角线为0无边为Inf这里要注意 % graph函数会将非零权重包括Inf视为边。所以我们的adj_mat需要处理。 % 正确做法将Inf替换为0表示无边。 adj_mat_for_graph adj_mat; adj_mat_for_graph(adj_mat_for_graphinf) 0; G2 graph(adj_mat_for_graph, upper); % ‘upper’表示使用上三角部分因为是无向对称矩阵 [dist_mat2, path_mat2] shortestpath(G2, 1, all); % 验证结果一致...shortestpath函数默认使用的就是Dijkstra算法对于非负权图。它的优势在于代码简洁一两行搞定。性能优化底层由C实现经过高度优化处理大规模图的速度远超我们自己写的脚本。功能丰富除了单源最短路径还可以方便地计算任意两点间的最短路径、最短路径树、判断连通性等。可视化集成plot(G)可以直接画出网络图非常直观。5.2 在数学建模中应用一个简单案例假设你在做一次数学建模竞赛题目涉及城市间的物资运输。你需要找到从中央仓库节点1到各个配送站的最短路径以最小化运输成本。数据以表格形式给出包含道路连接的起点、终点和运输成本。步骤数据预处理将表格数据读入MATLAB整理成边列表s, t, w。建图与计算使用graph(s,t,w)创建图然后用shortestpath计算。结果分析不仅得到距离还能得到路径用于生成运输路线图。应对变化如果题目中某条道路因故封闭成本变为Inf你只需要在边列表中移除该边或将其权重设为一个极大值重新计算即可。这种灵活性是图模型的巨大优势。% 模拟建模中的数据读取和计算 % 假设有一个CSV文件 ‘roads.csv’三列FromCity, ToCity, Cost % data readmatrix(roads.csv); % 读取数据 % s data(:,1); t data(:,2); w data(:,3); % 这里用模拟数据 s [1 1 2 2 3 4 5]; t [2 3 3 4 5 5 6]; w [4 2 5 10 3 4 6]; G graph(s, t, w); central_warehouse 1; [dist, path] shortestpath(G, central_warehouse, all); % 输出到每个站点的最优路线 for i 1:numnodes(G) fprintf(仓库 - 站点%d: 成本 %.1f, 路线 , i, dist(i)); fprintf(%d , path{i}); fprintf(\n); end % 可视化网络和最短路径树可选 figure; p plot(G, EdgeLabel, G.Edges.Weight, NodeLabel, 1:numnodes(G)); highlight(p, path{6}, EdgeColor, r, LineWidth, 2); % 高亮显示到站点6的路径 title(运输网络与到站点6的最短路径红色);5.3 从最短路径到更广阔的图论世界掌握了最短路径和MATLAB的基本操作你已经打开了图论建模的一扇大门。但这仅仅是开始。在图论的世界里还有更多强大的工具等待你去应用最小生成树Minimum Spanning Tree, MST用于连接所有顶点且总权重最小的树状子图。解决网络建设总成本最低的问题如光纤铺设、电路板布线。MATLAB函数minspantree(G)。最大流/最小割问题研究网络中的流量传输能力。解决交通流量、管道输送、信息传递的最大容量问题。MATLAB函数maxflow(G, source, sink)。拓扑排序针对有向无环图DAG给出一个线性的顶点序列使得对于每一条有向边(u,v)u在序列中都出现在v之前。常用于任务调度、课程安排。MATLAB中可通过digraph和toposort函数处理。中心性分析衡量网络中节点的重要性。包括度中心性、接近中心性、中介中心性等。这对于社交网络分析、关键基础设施识别至关重要。centrality函数族提供了多种计算方式。当你面对一个复杂的系统问题时不妨先问自己它能被抽象成点和边吗如果能那么图论很可能为你提供一套现成的、强大的分析框架。从MATLAB中这些易用的函数起步结合对算法原理的深入理解你就能在数学建模和实际工程中将复杂问题化繁为简找到最优解。