1. 项目概述当数学建模遇上图论Python如何成为解题利器搞数学建模的朋友尤其是参加过国赛、美赛或者亚太杯这类竞赛的肯定对“图论”这两个字不陌生。无论是2019年国赛C题“机场出租车”的调度优化还是2024年高教社杯C题可能涉及的物流网络分析甚至是2026年亚太杯A题这种未来赛题中潜在的城市规划问题图论模型都像一把万能钥匙能打开许多复杂系统的大门。但很多人在初次接触时会觉得图论算法抽象、实现复杂光是Dijkstra和Floyd这两个名字就让人头大。其实一旦你用Python这个工具把理论和代码连接起来就会发现它远没有想象中那么难。今天我就结合自己多年打比赛和做项目的经验来聊聊如何用Python玩转数学建模中的图论问题从基础概念到算法实现再到实战避坑给你讲透。简单来说图论就是研究“关系”的数学。点代表实体边代表实体间的联系。在数学建模中当你遇到“最短路径”、“最小成本”、“最大流”、“最优分配”这类关键词时就该立刻想到图论。而Python凭借其简洁的语法和强大的库如NetworkX能让你从繁琐的矩阵计算和指针操作中解放出来专注于模型构建和算法逻辑本身。这篇文章就是写给那些希望将图论从理论公式转化为手中利剑的建模者无论你是刚入门的新手还是想深化理解的老手都能找到可以直接“抄作业”的代码和思路。2. 图论基础与Python表示从抽象概念到具体代码在动手写算法之前我们必须把图在计算机里“画”出来。这里的“画”不是可视化而是数据结构化。不同的表示方法直接决定了后续算法的效率和实现的难易度。2.1 图的分类与核心概念图G通常表示为G(V, E)其中V是顶点集合E是边集合。根据边的性质我们可以进行多重分类无向图 vs 有向图边是否有方向。地铁线路图可以看作无向图双向通行而城市单行道网络则必须用有向图表示。加权图 vs 无权图边是否带有权重或成本、距离、时间等。最短路径问题一定是基于加权图的。连通图 vs 非连通图图中任意两点间是否存在路径。对于非连通图许多算法需要分别应用于其各个连通分量。在数学建模中最关键的一步就是问题抽象把实际问题中的对象抽象为顶点对象之间的关系抽象为边关系的度量抽象为权重。例如在“机场出租车”问题中候客点、航站楼、蓄车池可以看作顶点道路是边行驶时间或距离是权重。2.2 Python中的图表示方法邻接矩阵与邻接表Python中实现图主流有两种方式自己造轮子用基础数据结构和用专业库。我们先看看自己如何实现这能帮你理解底层原理。1. 邻接矩阵用一个二维列表或NumPy数组matrix表示。matrix[i][j]的值表示顶点i到顶点j的边的权重。对于无权图可以用1表示连通0表示不连通对于无向图矩阵是对称的。# 示例一个包含4个顶点的加权有向图 INF float(inf) # 代表无穷大即两点间没有直接边 graph_matrix [ [0, 2, 6, 4], [INF, 0, 3, INF], [7, INF, 0, 1], [5, INF, 12, 0] ] # graph_matrix[0][1] 2 表示从顶点0到顶点1的边权重为2。 # graph_matrix[1][3] INF 表示从顶点1到顶点3没有直接边。注意邻接矩阵非常适合稠密图边数量接近顶点数量的平方且能快速判断任意两点间是否有直接边。但其空间复杂度是O(V²)对于顶点数上万的大型稀疏图如社交网络会浪费大量内存。2. 邻接表这是更节省空间的方式特别适合稀疏图。我们用字典或列表的列表来表示adj_list[i]存储一个列表里面是所有从顶点i出发的边所指向的顶点及其权重。# 使用字典列表表示同一个图 graph_list { 0: [(1, 2), (2, 6), (3, 4)], 1: [(2, 3)], 2: [(0, 7), (3, 1)], 3: [(0, 5), (2, 12)] } # graph_list[0] 包含三条边到1权重2到2权重6到3权重4。邻接表的空间复杂度是O(VE)查询两个顶点是否直接相连的效率不如矩阵但遍历某个顶点的所有邻居非常高效。在大多数涉及遍历的算法如BFS、DFS、Dijkstra中邻接表是更优的选择。3. 专业库NetworkX对于数学建模我强烈推荐直接使用NetworkX库。它封装了图的数据结构和上百种经典算法让你能专注于建模逻辑。import networkx as nx # 创建一个有向图 G nx.DiGraph() # 添加带权重的边会自动添加顶点 G.add_weighted_edges_from([(0, 1, 2), (0, 2, 6), (0, 3, 4), (1, 2, 3), (2, 0, 7), (2, 3, 1), (3, 0, 5), (3, 2, 12)]) # 获取顶点1的所有出边信息 print(list(G.edges(1, dataTrue))) # 输出[(1, 2, {weight: 3})]NetworkX的优点是快、全、稳。在比赛时间有限的情况下它能极大提升开发效率。除非赛题有极特殊的性能要求或限制库的使用否则NetworkX应是首选。3. 最短路径算法精讲Dijkstra与Floyd的实战抉择最短路径是图论在建模中最常见的应用没有之一。Dijkstra和Floyd是两把不同的尺子量不同的距离。3.1 Dijkstra算法单源最短路径的标杆核心思想贪心策略。从一个源点出发逐步确定到其他所有顶点的最短距离。它要求边的权重非负。这是理解算法的关键前提因为一旦有负权边贪心选择的“当前最短路径”可能不是全局最短的。算法步骤与手动模拟 假设我们求上例中从顶点0出发到所有点的最短路径。初始化距离数组dist [0, INF, INF, INF]前驱数组prev [None, None, None, None]集合S包含已确定最短路径的顶点初始为空Q包含所有顶点。从Q中选出距离最小的顶点u初始为0。将u加入S。松弛操作遍历u的所有邻居v。如果dist[u] w(u, v) dist[v]则更新dist[v]和prev[v]。重复步骤2-3直到Q为空。手动推演后我们会得到从0到各点的最短距离[0, 2, 5, 4]。到顶点2的路径是0-1-2距离为5而不是直接边的6。Python实现使用优先队列优化 自己实现Dijkstra能加深理解。使用heapq优先队列可以将算法复杂度优化到 O((VE) log V)。import heapq def dijkstra(graph, start): :param graph: 邻接表表示的图graph[u] [(v, weight), ...] :param start: 源点 :return: dist (距离字典), prev (前驱字典) dist {node: float(inf) for node in graph} prev {node: None for node in graph} dist[start] 0 # 优先队列元素为 (距离, 顶点) pq [(0, start)] while pq: current_dist, u heapq.heappop(pq) # 如果当前取出的距离大于记录的距离说明是旧数据跳过 if current_dist dist[u]: continue for v, w in graph[u]: new_dist current_dist w if new_dist dist[v]: dist[v] new_dist prev[v] u heapq.heappush(pq, (new_dist, v)) return dist, prev # 使用之前定义的graph_list dist, prev dijkstra(graph_list, 0) print(距离:, dist) # 输出{0: 0, 1: 2, 2: 5, 3: 4}NetworkX一键调用# 计算单源最短路径长度 length nx.single_source_dijkstra_path_length(G, source0) print(length) # 输出{0: 0, 1: 2, 2: 5, 3: 4} # 计算具体路径 path nx.single_source_dijkstra_path(G, source0) print(path) # 输出{0: [0], 1: [0, 1], 2: [0, 1, 2], 3: [0, 3]}实操心得在建模中务必先检查权重是否为非负。例如如果边代表利润求“最大利润路径”可以通过将权重取负数转化为最短路径问题吗不可以因为Dijkstra不支持负权。这时需要考虑其他算法如Bellman-Ford或将其转化为网络流问题。3.2 Floyd算法全源最短路径的利器核心思想动态规划。定义dist[k][i][j]为只允许使用顶点0...k作为中间点从i到j的最短路径长度。通过三重循环逐步“允许”更多的顶点作为中转站最终找到任意两点间的最短路径。它能够处理负权边但不能有负权环。算法核心三重循环的奥秘其状态转移方程是理解的关键dist[k][i][j] min(dist[k-1][i][j], dist[k-1][i][k] dist[k-1][k][j])意思是从i到j且允许通过前k个顶点的最短路径要么不经过k继承上一状态要么经过ki-k的最短路径加上k-j的最短路径。实际编码中我们可以省略第一维直接在原矩阵上迭代。Python实现def floyd_warshall(graph_matrix): n len(graph_matrix) dist [row[:] for row in graph_matrix] # 创建副本防止修改原数据 # 中间节点k for k in range(n): # 起始节点i for i in range(n): # 终止节点j for j in range(n): # 如果通过k中转的路径更短则更新 if dist[i][k] dist[k][j] dist[i][j]: dist[i][j] dist[i][k] dist[k][j] return dist # 使用之前定义的邻接矩阵 result floyd_warshall(graph_matrix) for row in result: print(row) # 输出结果矩阵其中result[i][j]即为i到j的最短距离。NetworkX一键调用# 计算所有节点对之间的最短路径长度 lengths dict(nx.all_pairs_dijkstra_path_length(G)) # 注意这里用的仍是Dijkstra要求非负权 # 对于有负权但无负环的图可以使用nx.all_pairs_bellman_ford_path_length print(lengths[0][2]) # 输出顶点0到顶点2的最短距离5Dijkstra vs Floyd 如何选这是建模中的一个关键决策点。问题规模如果图非常大顶点数1000且只需要计算从一个或少数几个源点出发的最短路径绝对不要用Floyd。其O(V³)的复杂度是无法承受的。应该使用多次Dijkstra。需求场景如果需要频繁查询任意两点间的最短距离即全源最短路径并且图规模适中顶点数在几百以内那么Floyd预先计算好所有结果查询时就是O(1)的复杂度非常高效。权重特性如果存在负权边Dijkstra失效必须使用Floyd或Bellman-Ford。在“机场出租车”问题中如果需要计算蓄车池到各个航站楼的最短时间单源用Dijkstra。如果需要评估所有候客点两两之间的通行时间以备全局调度全源且点位不多可以考虑Floyd。4. 数学建模中的图论实战从问题抽象到代码求解掌握了工具我们来看怎么用。数学建模中的图论问题难点往往不在算法本身而在如何将一篇充满文字描述的问题转化为一个清晰的图模型。4.1 经典赛题场景拆解场景一路径规划与设施选址如2019年国赛C题“机场出租车”顶点出租车蓄车池、各个航站楼出口候客点、可能的关键道路交叉口。边连接这些点的道路有向边可能包含单行道。权重行驶时间距离/平均速度 可能的路口等待时间。这里权重必须非负。问题求蓄车池到最近可用候客点的最短时间单源最短路径。更进一步可能是多辆车、多个需求点的调度这就演变成了多源点最短路径或网络流问题。对于多源点可以对每个源点跑一次Dijkstra。场景二网络流与资源分配如物流配送、信息传输顶点仓库、配送中心、客户点。边运输路线具有容量最大运输量和成本单位流量费用。问题在满足客户需求的前提下如何安排运输使总成本最低这是经典的最小费用最大流问题。虽然NetworkX提供了最大流算法nx.maximum_flow和最小费用流算法nx.max_flow_min_cost但在建模中更常见的做法是将其转化为线性规划问题用PuLP或SciPy来求解因为这样能更方便地添加复杂的约束条件如时间窗、车辆载重限制。场景三拓扑排序与任务调度如项目安排、课程排序顶点任务或活动。有向边A-B表示任务A必须在任务B之前完成。问题是否存在一个合理的执行顺序这就是拓扑排序。如果图中存在环说明依赖关系矛盾项目不可执行。NetworkX的nx.topological_sort可以直接给出一个可行序列。4.2 一个完整的建模示例简易公交线路查询系统假设我们要为一个城市建立公交线路查询模型提供任意两站之间的最短乘车时间忽略等车时间只考虑行驶时间换乘惩罚。步骤1抽象建模将每个公交站点视为一个顶点。注意同一地理位置的换乘站如地铁站和公交站同名在图中应视为不同的顶点然后用一条权重很小的边代表换乘步行时间连接它们。在同一公交线路上相邻两站之间连一条有向边权重为区间行驶时间。通常需要连双向边。在换乘点连接代表不同线路站点的顶点权重为换乘时间如5分钟。步骤2数据准备与图构建假设我们有站点数据stations.csv和线路连接数据links.csv。import pandas as pd import networkx as nx # 读取数据 stations_df pd.read_csv(stations.csv) # 列station_id, station_name, is_transfer links_df pd.read_csv(links.csv) # 列line_id, from_station_id, to_station_id, travel_time G nx.Graph() # 创建无向图假设公交双向行驶时间相同 # 添加所有站点顶点 for _, row in stations_df.iterrows(): G.add_node(row[station_id], namerow[station_name]) # 添加线路边 for _, row in links_df.iterrows(): G.add_edge(row[from_station_id], row[to_station_id], weightrow[travel_time], linerow[line_id]) # 处理换乘为同一换乘点的不同站点间添加换乘边 transfer_penalty 5 # 换乘惩罚时间单位分钟 transfer_stations stations_df[stations_df[is_transfer]] # 假设有一个方法能找出属于同一换乘中心的站点组这里简化处理 transfer_groups [[1001, 1002], [2001, 2002, 2003]] # 示例每组内的站点可换乘 for group in transfer_groups: for i in range(len(group)): for j in range(i1, len(group)): G.add_edge(group[i], group[j], weighttransfer_penalty, linetransfer)步骤3算法求解与接口封装def find_shortest_path(graph, start_station_name, end_station_name): 根据站名查找最短路径 # 根据站名找到站点ID这里简化假设名称唯一 start_id stations_df[stations_df[name]start_station_name][id].values[0] end_id stations_df[stations_df[name]end_station_name][id].values[0] try: # 使用Dijkstra算法 path_length, path_nodes nx.single_source_dijkstra(graph, sourcestart_id, targetend_id) # 将节点ID转换回站名 path_names [stations_df.loc[stations_df[id]nid, name].values[0] for nid in path_nodes] return path_length, path_names except nx.NetworkXNoPath: return None, No path found # 查询示例 time, path find_shortest_path(G, 北京西站, 颐和园) print(f最短时间{time}分钟) print(f路径{ - .join(path)})步骤4模型评估与优化这个简易模型有很多可扩展的方向也正是建模论文中可以发挥的地方引入等车时间将边权重从固定行驶时间改为“行驶时间 平均等车时间/2”。等车时间与发车间隔有关。多目标优化用户可能不仅关心时间最短还关心换乘次数最少。这是一个多目标最短路径问题。可以给换乘边增加一个很大的惩罚权重将“换乘次数”转化为“换乘成本”加入到单目标中也可以通过k最短路径算法找出前几条备选路径供用户选择。动态权重考虑交通拥堵使边权重随时间变化。这需要引入时间片将静态图转化为动态图复杂度会大大增加。避坑指南在建模论文中描述图模型时一定要画出示意图用Visio、Draw.io甚至PPT画一张清晰的图标明顶点、边、权重的含义比大段文字描述有效十倍。同时在“模型假设”部分必须明确写出假设行驶时间恒定、忽略等车时间、换乘时间固定为5分钟等。这些假设是模型合理性的基础。5. 进阶算法与性能优化应对大规模复杂网络当问题规模变大或者模型需要更精细的描述时基础的最短路径可能不够用。5.1 处理负权边与检测负环Bellman-Ford算法如果图中有负权边比如某些路段有“补贴”走过反而减少成本Dijkstra算法会失效。这时需要使用Bellman-Ford算法。它的思想是对所有边进行V-1轮松弛操作理论上可以找到单源最短路径。如果在第V轮松弛还能更新说明图中存在负权回路沿着这个回路走成本可以无限降低此时最短路径问题无解。def bellman_ford(graph, start): 使用Bellman-Ford算法计算单源最短路径。 graph: 邻接表graph[u] [(v, w), ...] 返回 (dist, predecessor, has_negative_cycle) dist {node: float(inf) for node in graph} prev {node: None for node in graph} dist[start] 0 # 松弛 |V|-1 轮 for _ in range(len(graph) - 1): updated False for u in graph: for v, w in graph[u]: if dist[u] w dist[v]: dist[v] dist[u] w prev[v] u updated True if not updated: # 提前终止如果一轮没有更新 break # 检查负权环再进行一轮松弛如果还能更新则存在负环 has_negative_cycle False for u in graph: for v, w in graph[u]: if dist[u] w dist[v]: has_negative_cycle True break if has_negative_cycle: break return dist, prev, has_negative_cycle在数学建模中如果你构建的模型允许负权边一定要在论文中说明并解释其实际意义如补贴、奖励同时使用Bellman-Ford算法或说明如何规避负环。5.2 启发式搜索A*算法当图非常大时例如全国道路网Dijkstra算法会盲目地向所有方向扩展效率低下。A*算法是一种启发式搜索在Dijkstra的基础上增加了一个启发函数h(n)用于估计从当前顶点n到目标顶点的代价。算法会优先探索f(n) g(n) h(n)最小的顶点其中g(n)是从起点到n的实际代价。关键在于启发函数h(n)的设计。它必须满足可采纳性admissible即永远不高估实际代价。在路径规划中常用欧几里得距离或曼哈顿距离作为h(n)。import heapq import math def heuristic(a, b, pos): 启发函数欧几里得距离。pos是顶点坐标字典。 (x1, y1), (x2, y2) pos[a], pos[b] return math.sqrt((x1 - x2)**2 (y1 - y2)**2) def a_star(graph, start, goal, pos): open_set [] heapq.heappush(open_set, (0, start)) came_from {} g_score {node: float(inf) for node in graph} g_score[start] 0 f_score {node: float(inf) for node in graph} f_score[start] heuristic(start, goal, pos) while open_set: _, current heapq.heappop(open_set) if current goal: # 重构路径 path [] while current in came_from: path.append(current) current came_from[current] path.append(start) return path[::-1], g_score[goal] for neighbor, weight in graph[current]: tentative_g_score g_score[current] weight if tentative_g_score g_score[neighbor]: came_from[neighbor] current g_score[neighbor] tentative_g_score f_score[neighbor] tentative_g_score heuristic(neighbor, goal, pos) heapq.heappush(open_set, (f_score[neighbor], neighbor)) return None, float(inf) # 路径不存在在建模中如果问题有明显的几何位置信息如地图坐标使用A*算法可以极大加速搜索过程。论文中需要说明启发函数的选择及其可采纳性证明例如直线距离最短因此不会高估实际道路距离。5.3 使用第三方高性能库对于超大规模图百万顶点以上纯Python的NetworkX可能在内存和速度上遇到瓶颈。这时可以考虑以下方案Graph-tool一个基于C的高性能图库Python接口速度极快但安装稍复杂。Igraph另一个高性能图库有C核心支持多种语言。将问题转化为线性规划对于许多图论问题如最短路径、最大流、最小费用流其本质是线性规划的特例。使用专业的优化求解器如Gurobi, CPLEX或Python的PuLP、SciPy库可以处理更大规模的问题并且能轻松添加各种线性约束。这是数学建模高级阶段常用的方法。例如最短路径问题可以转化为一个0-1整数规划问题。设决策变量x_ij表示边(i, j)是否在路径上。目标是最小化∑ w_ij * x_ij约束条件是起点的流出量为1终点的流入量为1中间点的流入等于流出流量平衡。6. 常见问题、调试技巧与论文写作要点在实际编码和撰写论文时你会遇到很多坑。这里分享一些血泪教训。6.1 算法实现中的常见陷阱无穷大的表示使用float(inf)是标准做法。但在进行inf 某个负数或inf - inf运算时Python会得到inf或nan可能导致逻辑错误。在Floyd算法中更新距离时最好加一个判断if dist[i][k] INF and dist[k][j] INF: ...。图的连通性你的算法假设图是连通的吗对于非连通图Dijkstra或BFS/DFS只能得到它所在连通分量的信息。在初始化时所有未被访问的顶点距离应保持为无穷大。在论文中需要讨论非连通情况的处理例如给出“不可达”的提示。顶点索引自己用列表实现时务必确保顶点编号是从0开始的连续整数。如果原始数据顶点ID不连续或为字符串需要先建立映射字典。node_to_idx {node: i for i, node in enumerate(nodes)}。自定义比较函数在使用优先队列时如果距离相同Python的heapq会比较第二个元素顶点ID。如果顶点ID是不可比较的类型如自定义对象会导致错误。一个技巧是存入三元组(dist, count, node)其中count是一个自增的整数用于打破平局。6.2 建模与论文写作要点符号说明表这是论文的“钥匙”。必须清晰定义所有集合、参数、决策变量。例如G(V,E)图V为顶点集E为边集。w_{ij}边(i,j)的权重距离、时间、成本。d[i]从源点到顶点i的最短距离。x_{ij}0-1变量表示边(i,j)是否在路径中。模型假设这是论文的“安全区”。明确列出所有简化假设例如“假设各路段行驶速度恒定”、“忽略乘客上下车时间”、“假设换乘时间固定为5分钟”。这既能体现你考虑了实际情况又能保护模型不被过于严苛地审视。算法描述不要只贴代码用伪代码或清晰的步骤描述来说明核心算法。伪代码应介于自然语言和编程语言之间突出逻辑。例如描述Dijkstra算法1. 初始化距离数组dist[]全为INF源点dist[s]0优先队列pq中放入(0, s)。 2. 当pq非空 a. 弹出当前距离最小的顶点u。 b. 如果dist[u]小于弹出值跳过旧数据。 c. 遍历u的所有邻居v i. 计算新距离 new_dist dist[u] w(u, v)。 ii. 如果 new_dist dist[v]更新dist[v] new_dist记录前驱并将(new_dist, v)入队。 3. 返回dist数组和前驱数组。复杂度分析简要分析算法的时间和空间复杂度体现你对算法效率的把握。例如“本文采用的Dijkstra算法使用优先队列优化时间复杂度为O((VE) log V)其中V为站点数E为线路连接数在本题数据规模下可在毫秒级内完成计算。”可视化结果一图胜千言。用NetworkX的绘图功能nx.draw或Matplotlib将你的图模型、最终的最优路径清晰地画出来。在路径图中可以用高亮颜色标记出最短路径。6.3 调试与验证技巧构造微型测试用例不要一上来就用大赛给的几百个数据点测试。自己构造一个5-6个顶点的小图手动计算出最短路径然后用你的程序跑对比结果。这是最快定位逻辑错误的方法。打印中间状态在算法关键步骤如每轮松弛后打印dist数组观察其变化过程与手动模拟对比。使用NetworkX验证当你用自己的代码实现了一个算法后用NetworkX内置的相同算法再算一遍对比结果。这是验证正确性的“金标准”。边界条件测试起点和终点是同一个点。起点和终点不连通。图中只有一条边。权重全为0或存在负权。最后记住图论只是工具数学建模的核心是用数学语言描述世界用计算工具求解问题。Python和NetworkX让图论从深奥的数学理论变成了触手可及的解模利器。多练、多思考、多总结当下次赛题再出现“网络”、“路径”、“调度”、“分配”这些字眼时你就能从容地翻开图论这把工具箱选出最合适的那把螺丝刀。 Python图论算法实战：从Dijkstra到Floyd，数学建模核心工具详解
1. 项目概述当数学建模遇上图论Python如何成为解题利器搞数学建模的朋友尤其是参加过国赛、美赛或者亚太杯这类竞赛的肯定对“图论”这两个字不陌生。无论是2019年国赛C题“机场出租车”的调度优化还是2024年高教社杯C题可能涉及的物流网络分析甚至是2026年亚太杯A题这种未来赛题中潜在的城市规划问题图论模型都像一把万能钥匙能打开许多复杂系统的大门。但很多人在初次接触时会觉得图论算法抽象、实现复杂光是Dijkstra和Floyd这两个名字就让人头大。其实一旦你用Python这个工具把理论和代码连接起来就会发现它远没有想象中那么难。今天我就结合自己多年打比赛和做项目的经验来聊聊如何用Python玩转数学建模中的图论问题从基础概念到算法实现再到实战避坑给你讲透。简单来说图论就是研究“关系”的数学。点代表实体边代表实体间的联系。在数学建模中当你遇到“最短路径”、“最小成本”、“最大流”、“最优分配”这类关键词时就该立刻想到图论。而Python凭借其简洁的语法和强大的库如NetworkX能让你从繁琐的矩阵计算和指针操作中解放出来专注于模型构建和算法逻辑本身。这篇文章就是写给那些希望将图论从理论公式转化为手中利剑的建模者无论你是刚入门的新手还是想深化理解的老手都能找到可以直接“抄作业”的代码和思路。2. 图论基础与Python表示从抽象概念到具体代码在动手写算法之前我们必须把图在计算机里“画”出来。这里的“画”不是可视化而是数据结构化。不同的表示方法直接决定了后续算法的效率和实现的难易度。2.1 图的分类与核心概念图G通常表示为G(V, E)其中V是顶点集合E是边集合。根据边的性质我们可以进行多重分类无向图 vs 有向图边是否有方向。地铁线路图可以看作无向图双向通行而城市单行道网络则必须用有向图表示。加权图 vs 无权图边是否带有权重或成本、距离、时间等。最短路径问题一定是基于加权图的。连通图 vs 非连通图图中任意两点间是否存在路径。对于非连通图许多算法需要分别应用于其各个连通分量。在数学建模中最关键的一步就是问题抽象把实际问题中的对象抽象为顶点对象之间的关系抽象为边关系的度量抽象为权重。例如在“机场出租车”问题中候客点、航站楼、蓄车池可以看作顶点道路是边行驶时间或距离是权重。2.2 Python中的图表示方法邻接矩阵与邻接表Python中实现图主流有两种方式自己造轮子用基础数据结构和用专业库。我们先看看自己如何实现这能帮你理解底层原理。1. 邻接矩阵用一个二维列表或NumPy数组matrix表示。matrix[i][j]的值表示顶点i到顶点j的边的权重。对于无权图可以用1表示连通0表示不连通对于无向图矩阵是对称的。# 示例一个包含4个顶点的加权有向图 INF float(inf) # 代表无穷大即两点间没有直接边 graph_matrix [ [0, 2, 6, 4], [INF, 0, 3, INF], [7, INF, 0, 1], [5, INF, 12, 0] ] # graph_matrix[0][1] 2 表示从顶点0到顶点1的边权重为2。 # graph_matrix[1][3] INF 表示从顶点1到顶点3没有直接边。注意邻接矩阵非常适合稠密图边数量接近顶点数量的平方且能快速判断任意两点间是否有直接边。但其空间复杂度是O(V²)对于顶点数上万的大型稀疏图如社交网络会浪费大量内存。2. 邻接表这是更节省空间的方式特别适合稀疏图。我们用字典或列表的列表来表示adj_list[i]存储一个列表里面是所有从顶点i出发的边所指向的顶点及其权重。# 使用字典列表表示同一个图 graph_list { 0: [(1, 2), (2, 6), (3, 4)], 1: [(2, 3)], 2: [(0, 7), (3, 1)], 3: [(0, 5), (2, 12)] } # graph_list[0] 包含三条边到1权重2到2权重6到3权重4。邻接表的空间复杂度是O(VE)查询两个顶点是否直接相连的效率不如矩阵但遍历某个顶点的所有邻居非常高效。在大多数涉及遍历的算法如BFS、DFS、Dijkstra中邻接表是更优的选择。3. 专业库NetworkX对于数学建模我强烈推荐直接使用NetworkX库。它封装了图的数据结构和上百种经典算法让你能专注于建模逻辑。import networkx as nx # 创建一个有向图 G nx.DiGraph() # 添加带权重的边会自动添加顶点 G.add_weighted_edges_from([(0, 1, 2), (0, 2, 6), (0, 3, 4), (1, 2, 3), (2, 0, 7), (2, 3, 1), (3, 0, 5), (3, 2, 12)]) # 获取顶点1的所有出边信息 print(list(G.edges(1, dataTrue))) # 输出[(1, 2, {weight: 3})]NetworkX的优点是快、全、稳。在比赛时间有限的情况下它能极大提升开发效率。除非赛题有极特殊的性能要求或限制库的使用否则NetworkX应是首选。3. 最短路径算法精讲Dijkstra与Floyd的实战抉择最短路径是图论在建模中最常见的应用没有之一。Dijkstra和Floyd是两把不同的尺子量不同的距离。3.1 Dijkstra算法单源最短路径的标杆核心思想贪心策略。从一个源点出发逐步确定到其他所有顶点的最短距离。它要求边的权重非负。这是理解算法的关键前提因为一旦有负权边贪心选择的“当前最短路径”可能不是全局最短的。算法步骤与手动模拟 假设我们求上例中从顶点0出发到所有点的最短路径。初始化距离数组dist [0, INF, INF, INF]前驱数组prev [None, None, None, None]集合S包含已确定最短路径的顶点初始为空Q包含所有顶点。从Q中选出距离最小的顶点u初始为0。将u加入S。松弛操作遍历u的所有邻居v。如果dist[u] w(u, v) dist[v]则更新dist[v]和prev[v]。重复步骤2-3直到Q为空。手动推演后我们会得到从0到各点的最短距离[0, 2, 5, 4]。到顶点2的路径是0-1-2距离为5而不是直接边的6。Python实现使用优先队列优化 自己实现Dijkstra能加深理解。使用heapq优先队列可以将算法复杂度优化到 O((VE) log V)。import heapq def dijkstra(graph, start): :param graph: 邻接表表示的图graph[u] [(v, weight), ...] :param start: 源点 :return: dist (距离字典), prev (前驱字典) dist {node: float(inf) for node in graph} prev {node: None for node in graph} dist[start] 0 # 优先队列元素为 (距离, 顶点) pq [(0, start)] while pq: current_dist, u heapq.heappop(pq) # 如果当前取出的距离大于记录的距离说明是旧数据跳过 if current_dist dist[u]: continue for v, w in graph[u]: new_dist current_dist w if new_dist dist[v]: dist[v] new_dist prev[v] u heapq.heappush(pq, (new_dist, v)) return dist, prev # 使用之前定义的graph_list dist, prev dijkstra(graph_list, 0) print(距离:, dist) # 输出{0: 0, 1: 2, 2: 5, 3: 4}NetworkX一键调用# 计算单源最短路径长度 length nx.single_source_dijkstra_path_length(G, source0) print(length) # 输出{0: 0, 1: 2, 2: 5, 3: 4} # 计算具体路径 path nx.single_source_dijkstra_path(G, source0) print(path) # 输出{0: [0], 1: [0, 1], 2: [0, 1, 2], 3: [0, 3]}实操心得在建模中务必先检查权重是否为非负。例如如果边代表利润求“最大利润路径”可以通过将权重取负数转化为最短路径问题吗不可以因为Dijkstra不支持负权。这时需要考虑其他算法如Bellman-Ford或将其转化为网络流问题。3.2 Floyd算法全源最短路径的利器核心思想动态规划。定义dist[k][i][j]为只允许使用顶点0...k作为中间点从i到j的最短路径长度。通过三重循环逐步“允许”更多的顶点作为中转站最终找到任意两点间的最短路径。它能够处理负权边但不能有负权环。算法核心三重循环的奥秘其状态转移方程是理解的关键dist[k][i][j] min(dist[k-1][i][j], dist[k-1][i][k] dist[k-1][k][j])意思是从i到j且允许通过前k个顶点的最短路径要么不经过k继承上一状态要么经过ki-k的最短路径加上k-j的最短路径。实际编码中我们可以省略第一维直接在原矩阵上迭代。Python实现def floyd_warshall(graph_matrix): n len(graph_matrix) dist [row[:] for row in graph_matrix] # 创建副本防止修改原数据 # 中间节点k for k in range(n): # 起始节点i for i in range(n): # 终止节点j for j in range(n): # 如果通过k中转的路径更短则更新 if dist[i][k] dist[k][j] dist[i][j]: dist[i][j] dist[i][k] dist[k][j] return dist # 使用之前定义的邻接矩阵 result floyd_warshall(graph_matrix) for row in result: print(row) # 输出结果矩阵其中result[i][j]即为i到j的最短距离。NetworkX一键调用# 计算所有节点对之间的最短路径长度 lengths dict(nx.all_pairs_dijkstra_path_length(G)) # 注意这里用的仍是Dijkstra要求非负权 # 对于有负权但无负环的图可以使用nx.all_pairs_bellman_ford_path_length print(lengths[0][2]) # 输出顶点0到顶点2的最短距离5Dijkstra vs Floyd 如何选这是建模中的一个关键决策点。问题规模如果图非常大顶点数1000且只需要计算从一个或少数几个源点出发的最短路径绝对不要用Floyd。其O(V³)的复杂度是无法承受的。应该使用多次Dijkstra。需求场景如果需要频繁查询任意两点间的最短距离即全源最短路径并且图规模适中顶点数在几百以内那么Floyd预先计算好所有结果查询时就是O(1)的复杂度非常高效。权重特性如果存在负权边Dijkstra失效必须使用Floyd或Bellman-Ford。在“机场出租车”问题中如果需要计算蓄车池到各个航站楼的最短时间单源用Dijkstra。如果需要评估所有候客点两两之间的通行时间以备全局调度全源且点位不多可以考虑Floyd。4. 数学建模中的图论实战从问题抽象到代码求解掌握了工具我们来看怎么用。数学建模中的图论问题难点往往不在算法本身而在如何将一篇充满文字描述的问题转化为一个清晰的图模型。4.1 经典赛题场景拆解场景一路径规划与设施选址如2019年国赛C题“机场出租车”顶点出租车蓄车池、各个航站楼出口候客点、可能的关键道路交叉口。边连接这些点的道路有向边可能包含单行道。权重行驶时间距离/平均速度 可能的路口等待时间。这里权重必须非负。问题求蓄车池到最近可用候客点的最短时间单源最短路径。更进一步可能是多辆车、多个需求点的调度这就演变成了多源点最短路径或网络流问题。对于多源点可以对每个源点跑一次Dijkstra。场景二网络流与资源分配如物流配送、信息传输顶点仓库、配送中心、客户点。边运输路线具有容量最大运输量和成本单位流量费用。问题在满足客户需求的前提下如何安排运输使总成本最低这是经典的最小费用最大流问题。虽然NetworkX提供了最大流算法nx.maximum_flow和最小费用流算法nx.max_flow_min_cost但在建模中更常见的做法是将其转化为线性规划问题用PuLP或SciPy来求解因为这样能更方便地添加复杂的约束条件如时间窗、车辆载重限制。场景三拓扑排序与任务调度如项目安排、课程排序顶点任务或活动。有向边A-B表示任务A必须在任务B之前完成。问题是否存在一个合理的执行顺序这就是拓扑排序。如果图中存在环说明依赖关系矛盾项目不可执行。NetworkX的nx.topological_sort可以直接给出一个可行序列。4.2 一个完整的建模示例简易公交线路查询系统假设我们要为一个城市建立公交线路查询模型提供任意两站之间的最短乘车时间忽略等车时间只考虑行驶时间换乘惩罚。步骤1抽象建模将每个公交站点视为一个顶点。注意同一地理位置的换乘站如地铁站和公交站同名在图中应视为不同的顶点然后用一条权重很小的边代表换乘步行时间连接它们。在同一公交线路上相邻两站之间连一条有向边权重为区间行驶时间。通常需要连双向边。在换乘点连接代表不同线路站点的顶点权重为换乘时间如5分钟。步骤2数据准备与图构建假设我们有站点数据stations.csv和线路连接数据links.csv。import pandas as pd import networkx as nx # 读取数据 stations_df pd.read_csv(stations.csv) # 列station_id, station_name, is_transfer links_df pd.read_csv(links.csv) # 列line_id, from_station_id, to_station_id, travel_time G nx.Graph() # 创建无向图假设公交双向行驶时间相同 # 添加所有站点顶点 for _, row in stations_df.iterrows(): G.add_node(row[station_id], namerow[station_name]) # 添加线路边 for _, row in links_df.iterrows(): G.add_edge(row[from_station_id], row[to_station_id], weightrow[travel_time], linerow[line_id]) # 处理换乘为同一换乘点的不同站点间添加换乘边 transfer_penalty 5 # 换乘惩罚时间单位分钟 transfer_stations stations_df[stations_df[is_transfer]] # 假设有一个方法能找出属于同一换乘中心的站点组这里简化处理 transfer_groups [[1001, 1002], [2001, 2002, 2003]] # 示例每组内的站点可换乘 for group in transfer_groups: for i in range(len(group)): for j in range(i1, len(group)): G.add_edge(group[i], group[j], weighttransfer_penalty, linetransfer)步骤3算法求解与接口封装def find_shortest_path(graph, start_station_name, end_station_name): 根据站名查找最短路径 # 根据站名找到站点ID这里简化假设名称唯一 start_id stations_df[stations_df[name]start_station_name][id].values[0] end_id stations_df[stations_df[name]end_station_name][id].values[0] try: # 使用Dijkstra算法 path_length, path_nodes nx.single_source_dijkstra(graph, sourcestart_id, targetend_id) # 将节点ID转换回站名 path_names [stations_df.loc[stations_df[id]nid, name].values[0] for nid in path_nodes] return path_length, path_names except nx.NetworkXNoPath: return None, No path found # 查询示例 time, path find_shortest_path(G, 北京西站, 颐和园) print(f最短时间{time}分钟) print(f路径{ - .join(path)})步骤4模型评估与优化这个简易模型有很多可扩展的方向也正是建模论文中可以发挥的地方引入等车时间将边权重从固定行驶时间改为“行驶时间 平均等车时间/2”。等车时间与发车间隔有关。多目标优化用户可能不仅关心时间最短还关心换乘次数最少。这是一个多目标最短路径问题。可以给换乘边增加一个很大的惩罚权重将“换乘次数”转化为“换乘成本”加入到单目标中也可以通过k最短路径算法找出前几条备选路径供用户选择。动态权重考虑交通拥堵使边权重随时间变化。这需要引入时间片将静态图转化为动态图复杂度会大大增加。避坑指南在建模论文中描述图模型时一定要画出示意图用Visio、Draw.io甚至PPT画一张清晰的图标明顶点、边、权重的含义比大段文字描述有效十倍。同时在“模型假设”部分必须明确写出假设行驶时间恒定、忽略等车时间、换乘时间固定为5分钟等。这些假设是模型合理性的基础。5. 进阶算法与性能优化应对大规模复杂网络当问题规模变大或者模型需要更精细的描述时基础的最短路径可能不够用。5.1 处理负权边与检测负环Bellman-Ford算法如果图中有负权边比如某些路段有“补贴”走过反而减少成本Dijkstra算法会失效。这时需要使用Bellman-Ford算法。它的思想是对所有边进行V-1轮松弛操作理论上可以找到单源最短路径。如果在第V轮松弛还能更新说明图中存在负权回路沿着这个回路走成本可以无限降低此时最短路径问题无解。def bellman_ford(graph, start): 使用Bellman-Ford算法计算单源最短路径。 graph: 邻接表graph[u] [(v, w), ...] 返回 (dist, predecessor, has_negative_cycle) dist {node: float(inf) for node in graph} prev {node: None for node in graph} dist[start] 0 # 松弛 |V|-1 轮 for _ in range(len(graph) - 1): updated False for u in graph: for v, w in graph[u]: if dist[u] w dist[v]: dist[v] dist[u] w prev[v] u updated True if not updated: # 提前终止如果一轮没有更新 break # 检查负权环再进行一轮松弛如果还能更新则存在负环 has_negative_cycle False for u in graph: for v, w in graph[u]: if dist[u] w dist[v]: has_negative_cycle True break if has_negative_cycle: break return dist, prev, has_negative_cycle在数学建模中如果你构建的模型允许负权边一定要在论文中说明并解释其实际意义如补贴、奖励同时使用Bellman-Ford算法或说明如何规避负环。5.2 启发式搜索A*算法当图非常大时例如全国道路网Dijkstra算法会盲目地向所有方向扩展效率低下。A*算法是一种启发式搜索在Dijkstra的基础上增加了一个启发函数h(n)用于估计从当前顶点n到目标顶点的代价。算法会优先探索f(n) g(n) h(n)最小的顶点其中g(n)是从起点到n的实际代价。关键在于启发函数h(n)的设计。它必须满足可采纳性admissible即永远不高估实际代价。在路径规划中常用欧几里得距离或曼哈顿距离作为h(n)。import heapq import math def heuristic(a, b, pos): 启发函数欧几里得距离。pos是顶点坐标字典。 (x1, y1), (x2, y2) pos[a], pos[b] return math.sqrt((x1 - x2)**2 (y1 - y2)**2) def a_star(graph, start, goal, pos): open_set [] heapq.heappush(open_set, (0, start)) came_from {} g_score {node: float(inf) for node in graph} g_score[start] 0 f_score {node: float(inf) for node in graph} f_score[start] heuristic(start, goal, pos) while open_set: _, current heapq.heappop(open_set) if current goal: # 重构路径 path [] while current in came_from: path.append(current) current came_from[current] path.append(start) return path[::-1], g_score[goal] for neighbor, weight in graph[current]: tentative_g_score g_score[current] weight if tentative_g_score g_score[neighbor]: came_from[neighbor] current g_score[neighbor] tentative_g_score f_score[neighbor] tentative_g_score heuristic(neighbor, goal, pos) heapq.heappush(open_set, (f_score[neighbor], neighbor)) return None, float(inf) # 路径不存在在建模中如果问题有明显的几何位置信息如地图坐标使用A*算法可以极大加速搜索过程。论文中需要说明启发函数的选择及其可采纳性证明例如直线距离最短因此不会高估实际道路距离。5.3 使用第三方高性能库对于超大规模图百万顶点以上纯Python的NetworkX可能在内存和速度上遇到瓶颈。这时可以考虑以下方案Graph-tool一个基于C的高性能图库Python接口速度极快但安装稍复杂。Igraph另一个高性能图库有C核心支持多种语言。将问题转化为线性规划对于许多图论问题如最短路径、最大流、最小费用流其本质是线性规划的特例。使用专业的优化求解器如Gurobi, CPLEX或Python的PuLP、SciPy库可以处理更大规模的问题并且能轻松添加各种线性约束。这是数学建模高级阶段常用的方法。例如最短路径问题可以转化为一个0-1整数规划问题。设决策变量x_ij表示边(i, j)是否在路径上。目标是最小化∑ w_ij * x_ij约束条件是起点的流出量为1终点的流入量为1中间点的流入等于流出流量平衡。6. 常见问题、调试技巧与论文写作要点在实际编码和撰写论文时你会遇到很多坑。这里分享一些血泪教训。6.1 算法实现中的常见陷阱无穷大的表示使用float(inf)是标准做法。但在进行inf 某个负数或inf - inf运算时Python会得到inf或nan可能导致逻辑错误。在Floyd算法中更新距离时最好加一个判断if dist[i][k] INF and dist[k][j] INF: ...。图的连通性你的算法假设图是连通的吗对于非连通图Dijkstra或BFS/DFS只能得到它所在连通分量的信息。在初始化时所有未被访问的顶点距离应保持为无穷大。在论文中需要讨论非连通情况的处理例如给出“不可达”的提示。顶点索引自己用列表实现时务必确保顶点编号是从0开始的连续整数。如果原始数据顶点ID不连续或为字符串需要先建立映射字典。node_to_idx {node: i for i, node in enumerate(nodes)}。自定义比较函数在使用优先队列时如果距离相同Python的heapq会比较第二个元素顶点ID。如果顶点ID是不可比较的类型如自定义对象会导致错误。一个技巧是存入三元组(dist, count, node)其中count是一个自增的整数用于打破平局。6.2 建模与论文写作要点符号说明表这是论文的“钥匙”。必须清晰定义所有集合、参数、决策变量。例如G(V,E)图V为顶点集E为边集。w_{ij}边(i,j)的权重距离、时间、成本。d[i]从源点到顶点i的最短距离。x_{ij}0-1变量表示边(i,j)是否在路径中。模型假设这是论文的“安全区”。明确列出所有简化假设例如“假设各路段行驶速度恒定”、“忽略乘客上下车时间”、“假设换乘时间固定为5分钟”。这既能体现你考虑了实际情况又能保护模型不被过于严苛地审视。算法描述不要只贴代码用伪代码或清晰的步骤描述来说明核心算法。伪代码应介于自然语言和编程语言之间突出逻辑。例如描述Dijkstra算法1. 初始化距离数组dist[]全为INF源点dist[s]0优先队列pq中放入(0, s)。 2. 当pq非空 a. 弹出当前距离最小的顶点u。 b. 如果dist[u]小于弹出值跳过旧数据。 c. 遍历u的所有邻居v i. 计算新距离 new_dist dist[u] w(u, v)。 ii. 如果 new_dist dist[v]更新dist[v] new_dist记录前驱并将(new_dist, v)入队。 3. 返回dist数组和前驱数组。复杂度分析简要分析算法的时间和空间复杂度体现你对算法效率的把握。例如“本文采用的Dijkstra算法使用优先队列优化时间复杂度为O((VE) log V)其中V为站点数E为线路连接数在本题数据规模下可在毫秒级内完成计算。”可视化结果一图胜千言。用NetworkX的绘图功能nx.draw或Matplotlib将你的图模型、最终的最优路径清晰地画出来。在路径图中可以用高亮颜色标记出最短路径。6.3 调试与验证技巧构造微型测试用例不要一上来就用大赛给的几百个数据点测试。自己构造一个5-6个顶点的小图手动计算出最短路径然后用你的程序跑对比结果。这是最快定位逻辑错误的方法。打印中间状态在算法关键步骤如每轮松弛后打印dist数组观察其变化过程与手动模拟对比。使用NetworkX验证当你用自己的代码实现了一个算法后用NetworkX内置的相同算法再算一遍对比结果。这是验证正确性的“金标准”。边界条件测试起点和终点是同一个点。起点和终点不连通。图中只有一条边。权重全为0或存在负权。最后记住图论只是工具数学建模的核心是用数学语言描述世界用计算工具求解问题。Python和NetworkX让图论从深奥的数学理论变成了触手可及的解模利器。多练、多思考、多总结当下次赛题再出现“网络”、“路径”、“调度”、“分配”这些字眼时你就能从容地翻开图论这把工具箱选出最合适的那把螺丝刀。