数学建模竞赛必备：Dijkstra与Floyd算法实战解析

1. 项目概述：从实际问题到图论模型

在数学建模竞赛中，尤其是像国赛、美赛、亚太杯这类题目里，我们经常会遇到一类“空间关系”或“网络关系”问题。比如，题目可能描述一个城市的交通网络，要求你规划一条从A地到B地的最省时或最省钱的路线；或者，它可能描述一个社交网络，要求你找出影响力传播最快的路径；再或者，像“板凳龙闹元宵”这类富有文化背景的题目，也可能隐含着节点（板凳）之间的连接与移动路径优化问题。这些问题的本质，都可以抽象为“图”。

所谓“图”，在这里不是指函数图像，而是由“顶点”和“边”构成的一种数学模型。顶点代表我们研究的具体对象，比如交叉路口、城市、人、设备；边则代表对象之间的关系，比如道路、通信线路、社交关系。每条边通常还有一个“权值”，代表关系的某种度量，比如距离、时间、成本、流量。

本次我们要拆解的核心，就是图论中两个非常经典且实用的算法问题：最短路径和距离范围内点集搜索。这几乎是数学建模中处理图类问题的“标配”技能。最短路径帮你找到两点之间的最优连接，而范围搜索则帮你分析一个点的“辐射”或“影响”区域。很多赛题最终都会落到这两个计算的组合或变体上。掌握它们，意味着你能将复杂的现实问题，转化为清晰的、可计算的数学模型，这是从赛题描述走向编程求解的关键一步。

2. 核心思路与模型构建：如何将问题“画”成一张图

拿到一个赛题，第一步也是最关键的一步，就是建模。建模不是直接套算法，而是先理解问题，并将其转化为图论的语言。

2.1 问题抽象与图模型定义

我们以一个简化但典型的城市交通网络为例。假设有若干个公交站点，站点之间有道路相连，每条道路有固定的通行时间（分钟）。问题一：求从中心广场到火车站的最短通行时间。问题二：找出所有从中心广场出发，30分钟内可以到达的站点。

1. 定义顶点集 V：每个公交站点就是一个顶点。我们可以用数字编号（1, 2, 3, …）或者字符串名称（“Center”, “Station”）来标识它们。在编程中，通常使用从0或1开始的连续整数索引，这样便于用数组存储。

2. 定义边集 E 和权值 W：如果两个站点之间有直达道路，那么它们之间就有一条边。这条边的权值就是通行时间。这里有一个关键点：图是有向还是无向？如果所有道路都是双向且通行时间相同，那就是无向图，边 (A, B) 和 (B, A) 是等价的。如果存在单行道，或者上下坡时间不同，那就是有向图。在数学建模中，务必根据题意仔细区分。我们这个例子先按无向图处理。

3. 选择图的存储结构：这是将抽象模型转化为计算机可处理数据的关键。主要有两种方式：

• 邻接矩阵：一个n x n的二维数组（n为顶点数）。matrix[i][j]的值表示从顶点 i 到顶点 j 的边的权值。如果两点间没有直接边，通常用一个很大的数（如INF = 1e9）表示。对于无向图，矩阵是对称的。
  • 优点：直观，检查任意两点间是否有边、权值多少，速度极快（O(1)）。
  • 缺点：占用空间大（O(n²)），对于顶点很多但边很稀疏（比如社交网络，每个人只认识很少一部分人）的图，空间浪费严重。
• 邻接表：为每个顶点维护一个列表，记录它所有邻居顶点以及对应边的权值。可以用数组套链表、数组套动态数组（如C++的vector<pair<int, int>>）或字典（如Python的defaultdict(list)）来实现。
  • 优点：空间利用率高（O(V+E)），特别适合稀疏图。遍历一个点的所有邻居非常高效。
  • 缺点：判断任意两点间是否有边，需要遍历其中一个点的邻居列表，速度较慢（O(degree)）。

建模心得：在数学建模中，除非题目明确给出的是稠密矩阵数据，否则邻接表通常是更优选择。因为实际问题（交通网、社交网）大多是稀疏的。用邻接表在后续运行Dijkstra算法时，效率也更高。

2.2 算法选型背后的逻辑

为什么是Dijkstra和Floyd？它们解决的是同一类问题吗？并不完全是。

• 单源最短路径：求从一个特定的起点出发，到图中所有其他顶点的最短距离。这就是Dijkstra算法的战场。它像一个谨慎的探险家，从起点开始，一步步确认到每个点的最短距离，逐步向外扩张。对于问题一（求中心广场到火车站）和问题二（找30分钟内的所有点），我们都需要知道从起点（源）到其他点的距离。因此，运行一次Dijkstra算法就能同时得到这两个问题的答案，效率很高。
• 多源最短路径：求图中任意两个顶点之间的最短距离。这是Floyd-Warshall算法的专长。它通过动态规划的思想，考虑所有可能的中转点，来系统地更新任意两点间的最短距离。如果你需要频繁查询不同起点终点对的最短路径，或者需要获取全局的连通性信息（比如“网络的中心”在哪），Floyd是更好的选择。但它的时间复杂度是O(n³)，对于顶点数上千的图，计算压力会很大。

选择策略：

• 绝大多数情况用Dijkstra：数学建模赛题中，起点通常是明确的（如一个仓库、一个救援中心），我们需要分析它对整个网络的影响。跑一次Dijkstra足矣。
• 以下情况考虑Floyd：1) 顶点数很少（n < 200）。2) 题目要求你同时比较多个点作为起点的优劣（比如选一个物流中心，需要计算它到所有客户点的总距离）。3) 需要判断图的连通性（Floyd后，如果两点距离仍为无穷大，则不连通）。

3. 核心算法解析与实现细节

理解了模型和选型，我们来深入算法的内部，看看它们是如何工作的，并给出可以直接“抄作业”的代码模板。

3.1 Dijkstra算法：步步为营的最短路径探索

Dijkstra算法的核心思想是“贪心”。它维护一个集合S，里面是已经确定了最短距离的顶点。初始时，S只包含起点s，起点到自己的距离为0，到其他点的距离初始化为无穷大。

然后，它不断重复以下过程：

1. 从未确定的顶点集合中，选择一个当前距离起点最近的顶点u（这就是贪心选择）。
2. 将u加入已确定集合S。
3. 松弛操作：检查u的所有邻居v。如果“起点->u的距离 + u->v的边权”小于“当前记录的起点->v的距离”，就更新v的距离。这个操作可以理解为：“我发现了一条经过u到v的更短路径”。

如何高效地选出“当前距离起点最近的顶点”？这就需要用到优先队列（最小堆）。我们不需要每次遍历所有未确定点来找最小值，而是把（当前距离， 顶点）这个对子放入堆中，堆顶永远是目前距离最小的顶点。

Python实现模板（邻接表，使用heapq）：

import heapq def dijkstra(n, adj, start): """ :param n: 顶点数量，顶点编号从0到n-1 :param adj: 邻接表，adj[u] = [(v, weight), ...] :param start: 起点编号 :return: dist列表，dist[i]表示从start到i的最短距离 """ INF = float('inf') dist = [INF] * n dist[start] = 0 # 优先队列，元素为 (距离, 顶点) pq = [(0, start)] while pq: current_dist, u = heapq.heappop(pq) # 如果当前取出的距离大于记录的距离，说明这个节点已经被更优地更新过了，跳过 if current_dist > dist[u]: continue # 遍历邻居 for v, w in adj[u]: new_dist = current_dist + w if new_dist < dist[v]: dist[v] = new_dist heapq.heappush(pq, (new_dist, v)) return dist # 示例：构建一个无向图 n = 5 adj = [[] for _ in range(n)] edges = [(0, 1, 10), (0, 3, 5), (1, 2, 1), (1, 3, 2), (2, 4, 4), (3, 1, 3), (3, 2, 9), (3, 4, 2), (4, 0, 7), (4, 2, 6)] for u, v, w in edges: adj[u].append((v, w)) adj[v].append((u, w)) # 如果是无向图，需要添加双向边 start = 0 distances = dijkstra(n, adj, start) print(f"从顶点 {start} 到各点的最短距离：") for i, d in enumerate(distances): print(f" -> 顶点{i}: {d if d != INF else 'INF'}")

关键点与避坑指南：

1. if current_dist > dist[u]: continue这行至关重要！由于优先队列不支持直接修改元素，当我们更新某个顶点v的距离时，我们会将新的（更小的距离， v）压入堆。堆里可能同时存在v的多个不同距离的条目。这个判断语句确保我们只处理最早（即距离最小）的那个条目，后续更差的条目直接跳过。没有这行，算法逻辑正确但效率会降低。
2. 负权边是禁忌！Dijkstra算法基于贪心策略，假设“当前最短就是全局最短”。如果存在负权边，这个假设就不成立了，因为后续可能通过负权边让路径变得更短。Dijkstra无法处理含负权边的图，此时应使用Bellman-Ford或SPFA算法。
3. 时间复杂度：使用优先队列的Dijkstra算法时间复杂度为 O((V+E) log V)，其中V是顶点数，E是边数。这在稀疏图上非常高效。

3.2 Floyd-Warshall算法：全局视野的动态规划

Floyd算法的思想非常巧妙：它试图依次将每个顶点作为“中转站”，看看是否能让某些点对之间的路径变得更短。

定义dist[k][i][j]表示：只允许使用前k个顶点（编号1到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（即i->k的最短路径加上k->j的最短路径）。

实际上，我们可以用二维数组滚动更新，节省空间。

Python实现模板：

def floyd_warshall(n, adj_matrix): """ :param n: 顶点数量 :param adj_matrix: 邻接矩阵，adj_matrix[i][j]表示i到j的直接距离，无边时为INF，自身为0。 :return: dist矩阵，dist[i][j]为i到j的最短距离。 """ INF = float('inf') # 初始化距离矩阵为邻接矩阵的拷贝 dist = [row[:] for row in adj_matrix] # 核心三重循环 for k in range(n): # 中转点 for i in range(n): # 起点 if dist[i][k] == INF: # 一个小优化，如果i到k不通，则跳过 continue for j in range(n): # 终点 # 如果i->k和k->j是通的，尝试松弛 if dist[i][k] + dist[k][j] < dist[i][j]: dist[i][j] = dist[i][k] + dist[k][j] return dist # 示例：构建邻接矩阵 n = 4 INF = float('inf') # 初始化，自己到自己是0，其他为INF adj = [[INF]*n for _ in range(n)] for i in range(n): adj[i][i] = 0 # 添加边 edges = [(0, 1, 3), (0, 3, 7), (1, 0, 8), (1, 2, 2), (2, 0, 5), (2, 3, 1), (3, 0, 2)] for u, v, w in edges: adj[u][v] = w shortest_paths = floyd_warshall(n, adj) print("任意两点间最短距离矩阵：") for i in range(n): print([f'{shortest_paths[i][j]:2}' if shortest_paths[i][j] != INF else 'INF' for j in range(n)])

关键点与避坑指南：

1. 初始化：一定要将对角线（自己到自己）初始化为0。对于不直接相连的点，初始化为无穷大（INF）。INF的值要足够大，但要避免相加时溢出。通常用10**9或float(‘inf’)。
2. 循环顺序k, i, j是固定的！这个顺序保证了动态规划的正确性。k代表阶段（允许使用的前k个顶点），必须放在最外层。
3. 它能处理负权边，但不能处理负权环。Floyd算法可以处理带有负权边的图（这是它相对于Dijkstra的一个优势），但如果图中存在负权环（环上所有权重之和为负），那么最短路径的概念就失效了（可以无限绕环使距离趋于负无穷）。算法运行后，如果发现dist[i][i] < 0（自己到自己的距离变成了负数），就说明图中存在从i出发又能回到i的负权环。
4. 空间与时间：空间复杂度O(n²)，时间复杂度O(n³)。当n超过500时就需要非常谨慎，计算量可能成为瓶颈。

4. 问题二的求解：在某个距离范围内的点

解决了最短路径计算，问题二就变得非常简单。假设我们已经通过Dijkstra算法得到了从起点start到所有点的最短距离数组dist[]。

那么，找出所有在距离D范围内的点，只需要遍历dist数组：

def find_points_within_distance(dist, start, max_distance): """ :param dist: Dijkstra算法得到的距离列表 :param start: 起点（虽然dist就是基于start计算的，这里传入用于输出） :param max_distance: 距离阈值 :return: 在阈值内的点列表（包含起点） """ within_range = [] for i, d in enumerate(dist): if d <= max_distance and d != float('inf'): # 距离有效且在范围内 within_range.append((i, d)) # 可以同时记录点和距离 return within_range # 接续之前的Dijkstra示例 max_D = 9 points_in_range = find_points_within_distance(distances, start, max_D) print(f"\n从顶点 {start} 出发，距离不超过 {max_D} 的点有：") for point, d in points_in_range: print(f" 顶点{point}， 距离：{d}")

应用扩展：这个“范围搜索”功能非常有用。在数学建模中，它可以用来：

• 设施选址分析：一个消防站，其有效救援范围是5公里，找出所有能被覆盖的小区。
• 影响力分析：在社交网络中，一条信息从某个用户发出，在3层传播关系内（将边权视为1），能影响到哪些用户？
• 资源分配：确定一个配送中心在2小时车程内能服务哪些客户点。

5. 数学建模实战：从算法到论文

掌握了算法代码只是第一步，如何将其融入一篇完整的数学建模论文，才是竞赛取胜的关键。

5.1 模型建立部分的书写

在论文的“模型建立”部分，你需要清晰地阐述将实际问题转化为图论模型的过程。

1. 定义符号说明：首先建立一个符号表。

   • G = (V, E)表示图，其中V = {v1, v2, ..., vn}是顶点集合，E是边集合。
   • w(i, j)或w_ij表示顶点vi到vj的边的权值（距离、时间等）。若两点不直接相连，则w(i, j) = ∞。
   • d(i, j)表示从vi到vj的最短路径长度。
   • s表示路径起点。
   • D表示距离阈值。

2. 建立数学模型：

   • 最短路径模型：我们的目标是找到从起点s到终点t的一条路径P = (s, ..., t)，使得路径上所有边的权值之和∑ w(e)最小。这是一个优化问题。
   • Dijkstra算法描述：可以用集合论和递推公式来描述。定义集合S为已找到最短路径的顶点集。初始化S = {s},d(s)=0，对于其他顶点v，d(v)=w(s, v)。然后迭代：选取u ∈ V-S且d(u)最小者，将u加入S，并对u的所有邻居v进行松弛操作：d(v) = min(d(v), d(u) + w(u, v))。重复直至S = V或找到t。
   • 范围搜索模型：在得到所有d(s, v)后，满足条件的点集为：{ v ∈ V | d(s, v) ≤ D }。

论文技巧：配合一个简单的小型网络图（可以用Visio、PPT甚至手绘后扫描）作为示意图，能让模型描述更加清晰。在图中标出顶点、边权、起点和要求的范围，一目了然。

5.2 求解过程与结果分析

在“模型求解”部分，你需要说明你使用了什么工具（如Python+NetworkX库，或MATLAB，或C++），并简述算法步骤。不要直接贴大段代码，而是用伪代码或流程图展示核心逻辑。

结果展示建议：

1. 表格化数据：将起点到各点的最短距离用表格列出。
2. 可视化：这是极大的加分项。使用绘图库（如Python的matplotlib,networkx）将原网络和计算结果可视化。
   • 用节点大小或颜色表示是否在范围内。
   • 用高亮（如红色粗线）标出找到的最短路径。
   • 可以绘制从起点出发的距离等值线图或辐射状图，直观展示“范围”。
3. 分析：对结果进行简单分析。例如：“从中心广场到火车站的最短时间为12分钟，路径为A->B->C。在30分钟范围内，可以覆盖全市75%的主要站点，未能覆盖的站点集中在东北工业区，建议在该区域增设公交线路或站点。”

5.3 灵敏度分析与模型拓展

高级的论文会包含灵敏度分析和模型拓展，这体现了你对问题的深入思考。

• 灵敏度分析：探讨模型参数变化对结果的影响。例如：

  • 如果某条道路的通行时间因施工增加10%，最短路径会改变吗？总时间增加多少？
  • 距离阈值D从30分钟增加到35分钟，覆盖的站点数量会增加多少？增长率如何？
  • 这些分析可以通过修改权值或阈值，重新运行模型，对比结果来完成。

• 模型拓展：

  • 多目标优化：最短路径可能不止考虑时间，还有成本（过路费）、可靠性等。可以引入多权重，或者将其转化为单目标（如时间×成本系数）。
  • 动态网络：边权可能随时间变化（如拥堵）。可以引入时间片，将静态图转化为分层的时间-空间网络，再用最短路径算法。
  • “K短路径”问题：不仅求最短，还求第二短、第三短的路径，作为备选方案。这可以使用Yen’s算法。
  • 范围搜索的变体：不是找距离起点近的点，而是找距离一组起点（如多个仓库）最近的点，这可以转化为建立“超级源点”或分别计算后取最小值。

6. 常见问题与调试技巧实录

在实际编程和建模中，你肯定会遇到各种问题。下面是一些我踩过的坑和解决方法。

问题1：程序运行结果全是无穷大（INF）或者最短路径计算错误。

• 检查1：图的构建是否正确。这是最常见的问题。特别是用邻接表时，是否漏加了边？对于无向图，是否忘了添加反向边？打印出构建好的邻接表或邻接矩阵的前几行，人工核对。
• 检查2：权值的初始化。在Floyd算法中，是否将对角线初始化为0？是否将不存在的边初始化为一个足够大的INF（但不要大到相加溢出）？
• 检查3：Dijkstra的优先队列使用。是否遗漏了if current_dist > dist[u]: continue这行关键的剪枝？没有它，在复杂图上可能结果正确但会超时，在某些情况下也可能导致错误。
• 检查4：存在负权边。如果你的图有权值为负的边，Dijkstra算法会失效。确认题目条件，必要时换用Bellman-Ford算法。

问题2：算法运行超时。

• 顶点规模评估：Dijkstra + 堆 的时间复杂度是 O(E log V)。如果V和E在10^5级别，通常是可行的。如果超时，首先检查是否是死循环。
• Floyd的立方复杂度：如果顶点数n达到1000，Floyd的三重循环就是10^9次操作，在普通电脑上很容易超时。对于n>500的情况，应优先考虑使用Dijkstra算法（如果需要单源信息）或优化。
• 输入/输出效率：在C++/Java中，对于大规模数据（边数>10^5），使用cin/cout可能较慢，可以关闭流同步或用scanf/printf。在Python中，可以考虑使用sys.stdin.readline()。

问题3：如何记录最短路径而不仅仅是距离？Dijkstra和Floyd都可以方便地记录路径。

• Dijkstra：维护一个prev数组。在松弛操作if new_dist < dist[v]:成功时，不仅更新dist[v]，同时记录prev[v] = u。这意味着到v的最短路径是从u过来的。最后从终点t反向迭代prev数组直到起点s，即可得到路径。
• Floyd：同样维护一个next矩阵。初始化时，如果i和j有边，则next[i][j] = j，否则为-1。在松弛成功时，更新next[i][j] = next[i][k]。重构路径时，从i开始，不断跳转到next[i][j]，直到到达j。

问题4：如何将地理坐标（经纬度）转化为图论问题？很多赛题给的是点的经纬度坐标，而不是现成的网络。

1. 定义顶点：每个地理位置就是一个顶点。
2. 定义边与权值：这是关键。你需要根据题意决定哪些点之间应该有边。
   • 全连接：如果任何两点间都可以直接移动（如无人机投送），则构成一个完全图，边权为两点间的球面距离（如Haversine公式计算）。
   • 基于规则连接：如果只有距离小于一定阈值的点之间才有边（如通信基站），则需要计算所有点对距离，小于阈值则连边，权值即为该距离。
   • 使用路网：最复杂的情况。你需要额外的数据（道路Shapefile）来构建真实的道路网络，这通常超出初级建模范围，但可以简化为：将路口和兴趣点作为顶点，根据道路实际连接情况连边，权值为道路长度或预估时间。
3. 计算距离：使用Haversine公式计算经纬度间的球面距离。网上有现成的代码片段。记住，计算结果单位是公里或米，需要与题目要求的阈值单位统一。

最后，再分享一个我个人的小技巧：在数学建模比赛中，永远先实现一个针对小规模样例数据的、正确的版本。用题目给的简单样例验证你的模型和代码输出是否正确。确认无误后，再替换成完整的大数据集运行。这能帮你节省大量因逻辑错误而导致的调试时间。图论算法一旦正确，对于大数据集通常只是等待计算时间的问题。把基础打牢，才能从容应对赛题的各种变化。