XiaoMaColtAI/math-modeling-skill / dsh-plugin/math-modeling-agent/skills/math-modeling
math-modeling
Verified当用户要求数学建模、建模竞赛、建模分析、代码求解、结果可视化或生成数学建模论文时使用。支持完整三阶段流程、单独执行任一角色,以及在关键节点使用独立 Subagent 进行阶段内质检;默认只启用质检 Subagent,用户可明确选择额外协作。
| File | Kind | Size |
|---|---|---|
| SKILL.md | skill md | 10.5 KB |
| assets/01-优化算法说明.md | markdown | 79.1 KB |
| assets/02-预测类算法说明.md | markdown | 67.4 KB |
| assets/03-评价类算法说明.md | markdown | 81.6 KB |
| assets/04-图论与网络分析算法说明.md | markdown | 38.8 KB |
| assets/05-统计分析与数据处理算法说明.md | markdown | 60.7 KB |
| assets/06-综合类算法说明.md | markdown | 35.6 KB |
| assets/07-机器学习算法说明.md | markdown | 51.9 KB |
| assets/README.md | markdown | 9.1 KB |
| references/README.md | markdown | 2.1 KB |
| references/Subagent调度.md | markdown | 7.4 KB |
| references/交付与截止时间协议.md | markdown | 4.4 KB |
| references/算法索引.md | markdown | 1021 B |
| 使用指南.md | markdown | 3.4 KB |
assets/04-图论与网络分析算法说明.md
View on GitHub# 图论与网络分析算法说明文档
## 概述
图论与网络分析是数学建模中的重要算法类型,用于处理离散结构和网络优化问题。图论问题广泛存在于交通运输、通信网络、物流配送、社交网络等领域。
---
## 1. 最短路径问题 (Shortest Path Problem)
### 算法介绍
最短路径问题是指在给定网络图中,寻找两个顶点之间总权重最小的路径。
#### 1.1 Dijkstra算法
适用于**非负权图**,是求解单源最短路径的经典算法。
**核心思想**:贪心策略,每次选择距离源点最近的未访问顶点。
**算法步骤**:
1. 初始化:源点距离为0,其他顶点距离为∞
2. 选择未访问顶点中距离最小的顶点$u$
3. 松弛$u$的所有邻接边:若$dist[v] > dist[u] + w(u,v)$,则更新$dist[v]$
4. 重复2-3直到所有顶点都被访问
**时间复杂度**:$O((V+E)\log V)$(使用优先队列)
**距离更新公式**:
$$
dist[v] = \min\{dist[v], dist[u] + w(u, v)\}
$$
#### 1.2 Bellman-Ford算法
适用于**含负权边**的图,可检测负权回路。
**松弛操作**:
$$
dist[v] = \min\{dist[v], dist[u] + w(u, v)\}
$$
对所有边进行$|V|-1$轮松弛。
**时间复杂度**:$O(VE)$
#### 1.3 Floyd-Warshall算法
适用于**全源最短路径**,可处理负权边(不含负权回路)。
**状态转移方程**:
$$
dp[i][j][k] = \min\{dp[i][j][k-1], dp[i][k][k-1] + dp[k][j][k-1]\}
$$
简写为:
$$
dist[i][j] = \min\{dist[i][j], dist[i][k] + dist[k][j]\}
$$
**时间复杂度**:$O(V^3)$
### 适用范围
| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 路径规划 | 导航系统、物流配送 | 最小费用路径 |
| 网络路由 | 数据包路由 | 最快路径 |
| 交通规划 | 城市交通路径 | 最短时间/距离 |
| 供应链优化 | 供应商到工厂 | 最小成本 |
| 通信网络 | 信号传输路径 | 最小延迟 |
### 可视化图表类型
- **网络图**:顶点与边的可视化
- **路径标注图**:最短路径高亮显示
- **距离矩阵热力图**:顶点间距离
- **迭代过程图**:算法迭代过程
- **三维路径图**:三维空间中的路径
### 关键文献
| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| A note on two problems in connexion with graphs | Dijkstra | 1959 | Numerische Mathematik |
| Algorithm for the shortest path problem | Bellman | 1958 | Quarterly of Applied Mathematics |
| A Algorithm for Path Problems and Matrix Multiplication | Floyd | 1962 | Communications of the ACM |
### 代码实现要点
```python
import heapq
import numpy as np
import matplotlib.pyplot as plt
import networkx as nx
from matplotlib.patches import FancyArrowPatch
import warnings
warnings.filterwarnings('ignore')
# 设置中文字体 - 多字体备选防止渲染问题
plt.rcParams['font.sans-serif'] = ['SimHei', 'DejaVu Sans', 'Arial Unicode MS', 'Microsoft YaHei', 'Arial']
plt.rcParams['axes.unicode_minus'] = False
class ShortestPathAlgorithms:
"""
最短路径算法集合
"""
@staticmethod
def dijkstra(graph, start, end=None):
"""
Dijkstra最短路径算法
:param graph: 图的邻接表 {顶点: {邻居: 权重}}
:param start: 起点
:param end: 终点,若为None则计算到所有点的最短路径
:return: 最短距离字典, 前驱节点字典
"""
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
previous = {vertex: None for vertex in graph}
pq = [(0, start)]
visited = set()
while pq:
current_distance, current = heapq.heappop(pq)
if current in visited:
continue
visited.add(current)
if end and current == end:
break
for neighbor, weight in graph[current].items():
if neighbor in visited:
continue
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
previous[neighbor] = current
heapq.heappush(pq, (distance, neighbor))
return distances, previous
@staticmethod
def reconstruct_path(previous, start, end):
"""根据前驱节点重建路径"""
path = []
current = end
while current is not None:
path.append(current)
current = previous[current]
path.reverse()
return path if path[0] == start else []
@staticmethod
def bellman_ford(graph, start):
"""
Bellman-Ford算法(可处理负权边)
:param graph: 图的邻接表
:param start: 起点
:return: 最短距离字典, 前驱节点字典, 是否存在负权回路
"""
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
previous = {vertex: None for vertex in graph}
# 松弛操作 |V|-1 次
for _ in range(len(graph) - 1):
updated = False
for u in graph:
for v, weight in graph[u].items():
if distances[u] + weight < distances[v]:
distances[v] = distances[u] + weight
previous[v] = u
updated = True
if not updated:
break
# 检测负权回路
has_negative_cycle = False
for u in graph:
for v, weight in graph[u].items():
if distances[u] + weight < distances[v]:
has_negative_cycle = True
break
return distances, previous, has_negative_cycle
@staticmethod
def floyd_warshall(adjacency_matrix):
"""
Floyd-Warshall全源最短路径算法
:param adjacency_matrix: 邻接矩阵(inf表示不可达)
:return: 距离矩阵, 前驱矩阵
"""
n = len(adjacency_matrix)
dist = np.array(adjacency_matrix, dtype=float)
next_node = np.full((n, n), None, dtype=object)
# 初始化
for i in range(n):
for j in range(n):
if dist[i][j] != float('infinity') and i != j:
next_node[i][j] = j
if i == j:
dist[i][j] = 0
# 动态规划
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
next_node[i][j] = next_node[i][k]
return dist, next_node
@staticmethod
def reconstruct_floyd_path(next_node, start, end):
"""重建Floyd-Warshall路径"""
if next_node[start][end] is None:
return []
path = [start]
while start != end:
start = next_node[start][end]
path.append(start)
return path
def visualize_shortest_path(graph, start, end, shortest_path, distances):
"""可视化最短路径结果"""
fig, axes = plt.subplots(1, 2, figsize=(16, 7))
# 创建NetworkX图
G = nx.DiGraph()
for u in graph:
for v, weight in graph[u].items():
G.add_edge(u, v, weight=weight)
# 布局
pos = nx.spring_layout(G, k=2, iterations=50, seed=42)
# 图1:网络图和最短路径
ax1 = axes[0]
# 绘制所有边
edge_labels = {(u, v): f'{d["weight"]}' for u, v, d in G.edges(data=True)}
nx.draw_networkx_edges(G, pos, ax=ax1, edge_color='gray', alpha=0.5,
arrows=True, arrowsize=20, width=1.5)
# 高亮最短路径
if len(shortest_path) > 1:
path_edges = [(shortest_path[i], shortest_path[i+1])
for i in range(len(shortest_path)-1)]
nx.draw_networkx_edges(G, pos, ax=ax1, edgelist=path_edges,
edge_color='red', width=3, arrows=True, arrowsize=25)
# 绘制节点
node_colors = ['lightgreen' if node == start else 'lightcoral' if node == end
else 'lightblue' for node in G.nodes()]
nx.draw_networkx_nodes(G, pos, ax=ax1, node_color=node_colors,
node_size=800, edgecolors='black', linewidths=2)
nx.draw_networkx_labels(G, pos, ax=ax1, font_size=12, font_weight='bold')
# 边权重标签
nx.draw_networkx_edge_labels(G, pos, edge_labels, ax=ax1, font_size=9)
ax1.set_title(f'最短路径: {" -> ".join(shortest_path)}\n总距离: {distances[end]}', fontsize=14)
ax1.axis('off')
# 图2:距离分布
ax2 = axes[1]
# 从起点到各点的距离
nodes = list(distances.keys())
dists = [distances[n] if distances[n] != float('infinity') else 0 for n in nodes]
colors = ['green' if n == start else 'red' if n == end else 'skyblue' for n in nodes]
bars = ax2.bar(nodes, dists, color=colors, edgecolor='black', alpha=0.7)
# 添加数值标签
for bar, dist in zip(bars, dists):
if dist > 0:
height = bar.get_height()
ax2.text(bar.get_x() + bar.get_width()/2., height,
f'{dist:.0f}', ha='center', va='bottom', fontsize=10)
ax2.set_xlabel('节点', fontsize=12)
ax2.set_ylabel('最短距离', fontsize=12)
ax2.set_title(f'从 {start} 到各节点的最短距离', fontsize=14)
plt.tight_layout()
plt.savefig('shortest_path_results.png', dpi=150, bbox_inches='tight')
plt.show()
print("\n图表已保存为 'shortest_path_results.png'")
# 运行示例
if __name__ == "__main__":
print("=" * 60)
print("最短路径算法示例")
print("=" * 60)
# 示例图(城市交通网络)
graph = {
'A': {'B': 4, 'C': 2},
'B': {'C': 1, 'D': 5, 'E': 3},
'C': {'D': 8, 'E': 10},
'D': {'E': 2, 'F': 6},
'E': {'F': 3},
'F': {}
}
start_node = 'A'
end_node = 'F'
print(f"\n图结构:")
for node, neighbors in graph.items():
print(f" {node}: {neighbors}")
print(f"\n起点: {start_node}")
print(f"终点: {end_node}")
# Dijkstra算法
print("\n" + "=" * 60)
print("Dijkstra算法结果")
print("=" * 60)
spa = ShortestPathAlgorithms()
distances, previous = spa.dijkstra(graph, start_node, end_node)
shortest_path = spa.reconstruct_path(previous, start_node, end_node)
print(f"最短路径: {' -> '.join(shortest_path)}")
print(f"最短距离: {distances[end_node]}")
print("\n从起点到各节点的距离:")
for node, dist in sorted(distances.items()):
if dist != float('infinity'):
print(f" {start_node} -> {node}: {dist}")
# Floyd-Warshall算法
print("\n" + "=" * 60)
print("Floyd-Warshall算法结果")
print("=" * 60)
# 构建邻接矩阵
nodes = list(graph.keys())
n = len(nodes)
node_index = {node: i for i, node in enumerate(nodes)}
inf = float('infinity')
adj_matrix = [[inf] * n for _ in range(n)]
for i in range(n):
adj_matrix[i][i] = 0
for u in graph:
for v, weight in graph[u].items():
adj_matrix[node_index[u]][node_index[v]] = weight
dist_matrix, next_matrix = spa.floyd_warshall(adj_matrix)
print("全源最短距离矩阵:")
print(" ", " ".join([f"{node:4s}" for node in nodes]))
for i, node in enumerate(nodes):
row = [f"{dist_matrix[i][j]:4.0f}" if dist_matrix[i][j] != inf else " inf"
for j in range(n)]
print(f"{node}: ", " ".join(row))
# 可视化
visualize_shortest_path(graph, start_node, end_node, shortest_path, distances)
```
---
## 2. 最小生成树问题 (Minimum Spanning Tree, MST)
### 算法介绍
最小生成树是指在一个连通的无向图中,找到一棵包含所有顶点且总权重最小的树。
#### 2.1 Prim算法
从一个顶点开始,逐步添加权重最小的边,直到包含所有顶点。
**算法步骤**:
1. 选择任意顶点作为起始点
2. 在已访问顶点和未访问顶点之间找权重最小的边
3. 将该边和对应顶点加入树
4. 重复2-3直到所有顶点都被访问
**时间复杂度**:$O(E \log V)$(使用优先队列)
#### 2.2 Kruskal算法
按边的权重从小到大选择,不形成回路则加入,直到有$V-1$条边。
**算法步骤**:
1. 将所有边按权重排序
2. 从小到大选择边
3. 若边连接两个不同连通分量,则加入
4. 重复2-3直到有$V-1$条边
使用**并查集**检测回路。
**时间复杂度**:$O(E \log E)$
### 适用范围
| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 网络设计 | 通信网络、电力网络 | 连接成本最小 |
| 交通规划 | 道路建设规划 | 建设费用最小 |
| 管网布局 | 水管、气管布局 | 铺设成本最小 |
| 电路设计 | PCB布线 | 线路最短 |
| 聚类分析 | 层次聚类 | 相似度最大 |
### 可视化图表类型
- **生成树图**:MST边的高亮显示
- **构造过程图**:算法逐步构造过程
- **权重分布图**:边权重的分布
- **树状结构图**:MST的树形结构
- **对比图**:不同算法结果对比
### 关键文献
| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| Shortest connection networks and some generalizations | Prim | 1957 | Bell System Technical Journal |
| On the shortest spanning subtree of a graph and the traveling salesman problem | Kruskal | 1956 | Proceedings of the AMS |
### 代码实现要点
```python
import heapq
def prim(graph):
"""
Prim最小生成树算法
:param graph: 图的邻接表 {顶点: {邻居: 权重}}
:return: MST边列表, 总权重
"""
if not graph:
return [], 0
start = next(iter(graph.keys()))
visited = set([start])
edges = []
# 初始化优先队列
for neighbor, weight in graph[start].items():
heapq.heappush(edges, (weight, start, neighbor))
mst_edges = []
total_weight = 0
while edges and len(visited) < len(graph):
weight, u, v = heapq.heappop(edges)
if v in visited:
continue
visited.add(v)
mst_edges.append((u, v, weight))
total_weight += weight
for neighbor, w in graph[v].items():
if neighbor not in visited:
heapq.heappush(edges, (w, v, neighbor))
return mst_edges, total_weight
def kruskal(edges, vertices):
"""
Kruskal最小生成树算法
:param edges: 边列表 [(权重, 顶点1, 顶点2), ...]
:param vertices: 顶点集合
:return: MST边列表, 总权重
"""
# 并查集
parent = {v: v for v in vertices}
rank = {v: 0 for v in vertices}
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px == py:
return False
if rank[px] < rank[py]:
px, py = py, px
parent[py] = px
if rank[px] == rank[py]:
rank[px] += 1
return True
# 按权重排序
edges.sort()
mst_edges = []
total_weight = 0
for weight, u, v in edges:
if union(u, v):
mst_edges.append((u, v, weight))
total_weight += weight
if len(mst_edges) == len(vertices) - 1:
break
return mst_edges, total_weight
```
---
## 3. 网络流问题 (Network Flow Problem)
### 算法介绍
网络流问题研究在网络中从源点到汇点的最大流量。
#### 3.1 最大流问题
**基本概念**:
- **容量**:每条边的最大流量限制$c(u,v)$
- **流量**:每条边的实际流量$f(u,v)$
- **源点**:流出的起点$s$
- **汇点**:流入的终点$t$
**流量守恒**:
$$
\sum_{v} f(v, u) = \sum_{v} f(u, v), \quad \forall u \neq s, t
$$
**容量限制**:
$$
0 \leq f(u, v) \leq c(u, v)
$$
#### 3.2 Ford-Fulkerson算法
通过寻找增广路径增加流量,直到不存在增广路径。
**残差网络**:
$$
c_f(u, v) = \begin{cases}
c(u, v) - f(u, v), & \text{如果}(u, v) \in E \\
f(v, u), & \text{如果}(v, u) \in E \\
0, & \text{否则}
\end{cases}
$$
#### 3.3 Edmonds-Karp算法
Ford-Fulkerson的实现,使用BFS找增广路径。
**时间复杂度**:$O(VE^2)$
#### 3.4 Dinic算法
使用层次图和多路增广,效率更高。
**时间复杂度**:$O(V^2E)$
#### 3.5 最小费用最大流
在最大流的基础上使总费用最小。
**目标**:
$$
\min \sum_{(u,v) \in E} f(u, v) \cdot cost(u, v)
$$
### 适用范围
| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 交通流 | 城市交通流量 | 通行能力 |
| 物流配送 | 货物运输调度 | 运输量最大化 |
| 通信网络 | 数据传输 | 带宽分配 |
| 电力系统 | 电力调配 | 输电容量 |
| 项目调度 | 任务分配 | 资源分配 |
| 匹配问题 | 二分图匹配 | 转化为最大流 |
### 可视化图表类型
- **网络流图**:流量/容量标注
- **残差网络图**:残差容量可视化
- **增广路径图**:增广路径高亮
- **流量分配图**:流量分配情况
- **瓶颈分析图**:瓶颈边识别
### 关键文献
| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| Maximal Flow Through a Network | Ford & Fulkerson | 1956 | Canadian Journal of Mathematics |
| A new approach to the maximum flow problem | Edmonds & Karp | 1972 | Journal of the ACM |
| An algorithm for fast calculation of the best route | Dinic | 1970 | Soviet Math. Dokl. |
### 代码实现要点
```python
from collections import deque
class Edge:
def __init__(self, to, rev, capacity, cost=0):
self.to = to
self.rev = rev
self.capacity = capacity
self.cost = cost
class MaxFlow:
def __init__(self, n):
self.n = n
self.graph = [[] for _ in range(n)]
def add_edge(self, fr, to, cap, cost=0):
"""添加边"""
forward = Edge(to, len(self.graph[to]), cap, cost)
backward = Edge(fr, len(self.graph[fr]) - 1, 0, -cost)
self.graph[fr].append(forward)
self.graph[to].append(backward)
def max_flow_edmonds_karp(self, s, t):
"""Edmonds-Karp最大流"""
flow = 0
n = len(self.graph)
while True:
# BFS寻找增广路径
level = [-1] * n
queue = deque([s])
level[s] = 0
parent = [(-1, -1)] * n
while queue:
v = queue.popleft()
for i, edge in enumerate(self.graph[v]):
if edge.capacity > 0 and level[edge.to] < 0:
level[edge.to] = level[v] + 1
parent[edge.to] = (v, i)
queue.append(edge.to)
if level[t] < 0:
break
# 计算增广量
min_cap = float('inf')
v = t
while v != s:
p, i = parent[v]
edge = self.graph[p][i]
min_cap = min(min_cap, edge.capacity)
v = p
# 更新流量
v = t
while v != s:
p, i = parent[v]
edge = self.graph[p][i]
edge.capacity -= min_cap
self.graph[v][edge.rev].capacity += min_cap
v = p
flow += min_cap
return flow
def min_cost_max_flow(self, s, t, maxf=float('inf')):
"""最小费用最大流(Successive Shortest Path算法)"""
n = len(self.graph)
res = 0
h = [0] * n # 势能
prevv = [0] * n
preve = [0] * n
flow = 0
while flow < maxf:
# Dijkstra算法
dist = [float('inf')] * n
dist[s] = 0
in_queue = [False] * n
queue = deque([s])
in_queue[s] = True
while queue:
v = queue.popleft()
in_queue[v] = False
for i, edge in enumerate(self.graph[v]):
if edge.capacity > 0 and dist[edge.to] > dist[v] + edge.cost + h[v] - h[edge.to]:
dist[edge.to] = dist[v] + edge.cost + h[v] - h[edge.to]
prevv[edge.to] = v
preve[edge.to] = i
if not in_queue[edge.to]:
queue.append(edge.to)
in_queue[edge.to] = True
if dist[t] == float('inf'):
break
for v in range(n):
if dist[v] < float('inf'):
h[v] += dist[v]
# 计算增广量
d = maxf - flow
v = t
while v != s:
d = min(d, self.graph[prevv[v]][preve[v]].capacity)
v = prevv[v]
flow += d
res += d * h[t]
# 更新残差网络
v = t
while v != s:
edge = self.graph[prevv[v]][preve[v]]
edge.capacity -= d
self.graph[v][edge.rev].capacity += d
v = prevv[v]
return flow, res
```
---
## 4. 关键路径问题 (Critical Path Method, CPM)
### 算法介绍
关键路径法用于项目管理中确定项目完成的最短时间和关键活动。
**基本概念**:
- **活动**:项目中的任务
- **持续时间**:活动需要的时间
- **最早开始时间(ES)**:活动可以开始的最早时间
- **最早完成时间(EF)**:$EF = ES + 持续时间$
- **最晚完成时间(LF)**:活动必须完成的最晚时间
- **最晚开始时间(LS)**:$LS = LF - 持续时间$
- **总时差**:$TF = LS - ES = LF - EF$
**关键路径**:总时差为0的活动组成的路径。
### 算法步骤
#### 正向计算(最早时间)
1. $ES_{start} = 0$
2. $EF_i = ES_i + 持续时间_i$
3. $ES_j = \max\{EF_i\}$(所有前驱活动$i$)
#### 反向计算(最晚时间)
1. $LF_{end} = EF_{end}$
2. $LS_i = LF_i - 持续时间_i$
3. $LF_i = \min\{LS_j\}$(所有后继活动$j$)
### 适用范围
| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 项目管理 | 工程项目进度 | 活动依赖关系 |
| 生产调度 | 车间作业调度 | 工序约束 |
| 软件开发 | 软件项目计划 | 任务依赖 |
| 建筑工程 | 建筑进度规划 | 工序安排 |
| 活动策划 | 大型活动筹备 | 时间管理 |
### 可视化图表类型
- **网络图**:活动依赖关系图
- **甘特图**:活动时间安排
- **关键路径图**:关键路径高亮
- **时差分析图**:各活动时差
- **PERT图**:不确定时间的项目管理
### 关键文献
| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| Critical-Path Planning and Scheduling | Kelley & Walker | 1959 | Proceedings of the Eastern Joint Computer Conference |
### 代码实现要点
```python
import networkx as nx
import matplotlib.pyplot as plt
def critical_path_method(activities):
"""
关键路径法
:param activities: 活动列表 {活动名: {'duration': 持续时间, 'predecessors': [前驱活动]}}
:return: 关键路径, 各活动时间参数
"""
# 创建有向图
G = nx.DiGraph()
# 添加活动节点
for activity, data in activities.items():
G.add_node(activity, duration=data['duration'])
# 添加依赖关系边
for activity, data in activities.items():
for pred in data['predecessors']:
G.add_edge(pred, activity)
# 拓扑排序
topo_order = list(nx.topological_sort(G))
# 正向计算(最早时间)
ES = {}
EF = {}
for activity in topo_order:
duration = activities[activity]['duration']
predecessors = list(G.predecessors(activity))
if predecessors:
ES[activity] = max(EF[pred] for pred in predecessors)
else:
ES[activity] = 0
EF[activity] = ES[activity] + duration
# 反向计算(最晚时间)
LF = {activity: EF[activity] for activity in reversed(topo_order)}
LS = {}
for activity in reversed(topo_order):
duration = activities[activity]['duration']
successors = list(G.successors(activity))
if successors:
LF[activity] = min(LS[succ] for succ in successors)
LS[activity] = LF[activity] - duration
# 计算总时差
TF = {activity: LS[activity] - ES[activity] for activity in activities}
# 找出关键路径(时差为0的活动)
critical_activities = [act for act in activities if TF[act] == 0]
# 构建关键路径
critical_path = []
for act in critical_activities:
if not list(G.predecessors(act)): # 起点
path = [act]
current = act
while list(G.successors(current)):
for succ in G.successors(current):
if succ in critical_activities:
path.append(succ)
current = succ
break
if len(path) > len(critical_path):
critical_path = path
# 汇总时间参数
time_params = {}
for activity in activities:
time_params[activity] = {
'ES': ES[activity],
'EF': EF[activity],
'LS': LS[activity],
'LF': LF[activity],
'TF': TF[activity]
}
return critical_path, time_params
```
---
## 5. 欧拉路径与哈密顿路径
### 算法介绍
#### 5.1 欧拉路径
**定义**:经过图中每条边恰好一次的路径。
**存在条件**:
- 欧拉回路:所有顶点度数为偶数
- 欧拉路径:恰好两个顶点度数为奇数
**Fleury算法**:
1. 选择起点(度数为奇数的顶点或任意顶点)
2. 沿边前进,避免走桥边(除非无其他选择)
3. 直到回到起点(回路)或无法继续
**Hierholzer算法**:
1. 从任意顶点开始,沿边前进回到起点形成回路
2. 若有未访问边,将回路分解并合并
#### 5.2 哈密顿路径
**定义**:经过图中每个顶点恰好一次的路径。
**哈密顿回路**:起点和终点相同的哈密顿路径。
**NP完全问题**:没有多项式时间算法。
**求解方法**:
- 回溯法(小规模)
- 动态规划(中等规模)
- 启式算法(大规模)
### 适用范围
| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 路线规划 | 邮递员送信 | 中国邮递员问题 |
| 巡回路线 | 巡检路线 | 经过每条边 |
| 环球旅行 | 旅游规划 | 经过每个城市 |
| 基因测序 | DNA片段组装 | 超级路径问题 |
| 电路设计 | PCB布线 | 笔画问题 |
### 可视化图表类型
- **路径图**:欧拉/哈密顿路径可视化
- **度数分布图**:顶点度数分布
- **搜索树图**:回溯搜索过程
- **对比图**:欧拉路径vs哈密顿路径
### 关键文献
| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| Solutio problematis ad geometriam situs pertinentis | Euler | 1736 | Commentarii Academiae |
| On the Hamiltonian Game | Hamilton | 1857 | Icosian Game |
### 代码实现要点
```python
def has_eulerian_path(graph):
"""判断是否存在欧拉路径"""
odd_degree_count = 0
for vertex in graph:
if len(graph[vertex]) % 2 != 0:
odd_degree_count += 1
return odd_degree_count == 0 or odd_degree_count == 2
def hierholzer_eulerian_circuit(graph, start):
"""Hierholzer算法找欧拉回路"""
circuit = []
stack = [start]
current_path = {vertex: list(neighbors) for vertex, neighbors in graph.items()}
while stack:
current = stack[-1]
if current_path[current]:
next_vertex = current_path[current].pop()
stack.append(next_vertex)
else:
circuit.append(stack.pop())
return circuit[::-1]
def hamiltonian_path(graph):
"""回溯法找哈密顿路径"""
vertices = list(graph.keys())
n = len(vertices)
path = []
visited = set()
def backtrack(current):
path.append(current)
visited.add(current)
if len(path) == n:
return True
for neighbor in graph[current]:
if neighbor not in visited:
if backtrack(neighbor):
return True
visited.remove(current)
path.pop()
return False
for start in vertices:
if backtrack(start):
return path
return None
def tsp_dynamic_programming(dist_matrix):
"""
TSP 动态规划(Held-Karp),精确解,适用 n ≤ 20
:param dist_matrix: 距离矩阵 shape (n,n)
:return: 最短路径长度, 路径
"""
n = len(dist_matrix)
# dp[mask][i]: 已访问 mask 集合、最后在 i 的最短长度
dp = [[float('inf')] * n for _ in range(1 << n)]
parent = [[None] * n for _ in range(1 << n)]
dp[1][0] = 0 # 从城市 0 出发
for mask in range(1 << n):
for i in range(n):
if not (mask >> i) & 1 or dp[mask][i] == float('inf'):
continue
for j in range(n):
if (mask >> j) & 1:
continue
new_mask = mask | (1 << j)
nd = dp[mask][i] + dist_matrix[i][j]
if nd < dp[new_mask][j]:
dp[new_mask][j] = nd
parent[new_mask][j] = i
full = (1 << n) - 1
best = min(dp[full][i] + dist_matrix[i][0] for i in range(1, n))
last_i = min(range(1, n), key=lambda i: dp[full][i] + dist_matrix[i][0])
# 回溯路径:从最后到达的城市 last_i 倒推到起点 0
path = []
mask, cur = full, last_i
while cur is not None:
path.append(cur)
prev = parent[mask][cur]
mask ^= (1 << cur)
cur = prev
path = path[::-1] # 现在是 [0, ..., last_i]
path.append(0) # 回到起点,形成回路
return best, path
def tsp_nearest_neighbor(dist_matrix):
"""
TSP 最近邻启发式,快速近似解,适用大规模
:param dist_matrix: 距离矩阵 shape (n,n)
:return: 近似最短长度, 路径
"""
n = len(dist_matrix)
visited = [False] * n
visited[0] = True
path = [0]
cur = 0
total = 0.0
for _ in range(n - 1):
# 选最近的未访问城市
nxt = min((j for j in range(n) if not visited[j]),
key=lambda j: dist_matrix[cur][j])
total += dist_matrix[cur][nxt]
visited[nxt] = True
path.append(nxt)
cur = nxt
total += dist_matrix[cur][0]
path.append(0)
return total, path
def chinese_postman(graph):
"""
中国邮递员问题(边邮路,把奇数度顶点对加边后求欧拉回路)
:param graph: 邻接表 {u: [(v, weight), ...]},要求连通图
:return: 最短邮路长度, 是否可直接欧拉回路
"""
vertices = list(graph.keys())
odd = [v for v in vertices if len(graph[v]) % 2 != 0]
if len(odd) == 0:
return 0.0, True # 已是欧拉图
if len(odd) % 2 != 0:
raise ValueError("奇数度顶点数必须为偶数(握手定理),输入图不合法")
# 用 Floyd 求奇数度顶点间最短距离,做最小权完美匹配(简单贪心近似)
dist = {v: {u: float('inf') for u in vertices} for v in vertices}
for v in vertices:
dist[v][v] = 0
for u, w in graph[v]:
dist[v][u] = min(dist[v][u], w)
for k in vertices:
for i in vertices:
for j in vertices:
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
# 贪心匹配奇数度顶点(近似解;精确可用最小权完美匹配)
matched = set()
extra = 0.0
for i in range(len(odd)):
if odd[i] in matched:
continue
best_j, best_d = None, float('inf')
for j in range(i + 1, len(odd)):
if odd[j] in matched:
continue
d = dist[odd[i]][odd[j]]
if d < best_d:
best_j, best_d = odd[j], d
matched.add(odd[i]); matched.add(best_j)
extra += best_d
base = sum(w for u in graph for _, w in graph[u]) / 2 # 原边总长
return base + extra, False
def astar_search(graph, start, goal, heuristic):
"""
A* 搜索(有启发函数的最短路径)
:param graph: 邻接表 {u: [(v, weight), ...]}
:param start: 起点
:param goal: 终点
:param heuristic: 启发函数 h(node) → 到目标估计值(可采纳时最优)
:return: 路径列表, 总代价
"""
import heapq
open_set = [(heuristic(start), 0, start, [start])]
visited = set()
while open_set:
f, g, node, path = heapq.heappop(open_set)
if node in visited:
continue
visited.add(node)
if node == goal:
return path, g
for nxt, w in graph[node]:
if nxt not in visited:
heapq.heappush(open_set, (g + w + heuristic(nxt), g + w, nxt, path + [nxt]))
return None, float('inf')
```
---
## 6. 匹配问题
### 算法介绍
匹配是指图中一组没有公共顶点的边。
#### 6.1 二分图最大匹配
**定义**:在二分图中找边数最多的匹配。
**匈牙利算法**:
1. 初始匹配为空
2. 寻找增广路径
3. 沿增广路径增加匹配
4. 重复直到无增广路径
**时间复杂度**:$O(VE)$
#### 6.2 最大权匹配
在带权图中找总权重最大的匹配。
**KM算法**(Kuhn-Munkres):
- 适用于完全二分图
- 使用顶标和相等子图
- 时间复杂度:$O(V^3)$
### 适用范围
| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 任务分配 | 人员分配任务 | 二分图匹配 |
| 婚姻匹配 | 男女婚配 | 稳定匹配 |
| 课程排课 | 教师课程分配 | 匹配问题 |
| 器官移植 | 供体受体匹配 | 权重匹配 |
| 运输调度 | 司机车辆分配 | 最大权匹配 |
### 可视化图表类型
- **二分图**:二分图结构可视化
- **匹配边图**:匹配边高亮
- **增广路径图**:增广路径显示
- **权重标注图**:边的权重标注
### 关键文献
| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| The Hungarian Method for the assignment problem | Kuhn | 1955 | Naval Research Logistics Quarterly |
| Algorithms for the assignment and transportation problems | Munkres | 1957 | Journal of the SIAM |
### 代码实现要点
```python
def hungarian_algorithm(cost_matrix):
"""
匈牙利算法解决指派问题
:param cost_matrix: 成本矩阵
:return: 最小成本匹配
"""
n = len(cost_matrix)
cost_matrix = [row[:] for row in cost_matrix] # 深拷贝
# 初始化
u = [0] * (n + 1)
v = [0] * (n + 1)
matching = [0] * (n + 1)
# 行约减
for i in range(1, n + 1):
u[i] = min(cost_matrix[i - 1])
# 列约减
for j in range(1, n + 1):
v[j] = min(cost_matrix[i - 1][j - 1] - u[i] for i in range(1, n + 1))
# 寻找匹配
for i in range(1, n + 1):
while True:
# 构建相等子图
used = [False] * (n + 1)
min_slack = [float('inf')] * (n + 1)
parent = [0] * (n + 1)
def dfs(x):
used[x] = True
for y in range(1, n + 1):
if not used[y]:
slack = cost_matrix[x - 1][y - 1] - u[x] - v[y]
if slack < min_slack[y]:
min_slack[y] = slack
parent[y] = x
if matching[y] == 0 or dfs(matching[y]):
matching[y] = x
return True
return False
if dfs(i):
break
# 更新顶标
delta = min(min_slack[y] for y in range(1, n + 1) if not used[y])
for x in range(1, n + 1):
if used[x]:
u[x] += delta
for y in range(1, n + 1):
if used[y]:
v[y] -= delta
# 构建匹配结果
result = []
for j in range(1, n + 1):
if matching[j] != 0:
result.append((matching[j] - 1, j - 1))
total_cost = sum(cost_matrix[i][j] for i, j in result)
return total_cost, [(i, j) for i, j in result]
```
---
## 图论算法选择指南
### 按问题类型选择
| 问题类型 | 推荐算法 | 说明 |
|---------|---------|------|
| 两点最短路径 | Dijkstra | 非负权图 |
| 含负权最短路 | Bellman-Ford | 可检测负权回路 |
| 全源最短路 | Floyd-Warshall | 稠密图 |
| 连接所有顶点最小成本 | Prim/Kruskal | 最小生成树 |
| 最大传输能力 | 最大流算法 | Edmonds-Karp/Dinic |
| 最小费用传输 | 最小费用最大流 | 考虑费用 |
| 项目最短完成时间 | 关键路径法 | CPM/PERT |
| 经过所有点/边 | 欧拉/哈密顿路径 | 特殊路径 |
| 两两配对 | 二分图匹配 | 匈牙利算法 |
### 按图的特征选择
| 图特征 | 推荐算法 |
|---------|---------|
| 稀疏图 | 邻接表存储、Kruskal |
| 稠密图 | 邻接矩阵存储、Prim、Floyd-Warshall |
| 非负权 | Dijkstra |
| 含负权 | Bellman-Ford |
| 有向图 | Dijkstra、Bellman-Ford、网络流 |
| 无向图 | Prim、Kruskal |
| 树结构 | DFS、BFS |
| 二分图 | 匈牙利算法、最大流 |
### 按数据规模选择
| 规模 | 推荐算法 |
|------|---------|
| 小规模(<100顶点) | Floyd-Warshall、暴力搜索 |
| 中规模(100-10000) | Dijkstra、Prim、Edmonds-Karp |
| 大规模(>10000) | 优化的Dijkstra、A*算法 |
---
## 参考文献
1. Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. *Numerische Mathematik*, 1(1), 269-271.
2. Floyd, R. W. (1962). Algorithm 97: shortest path. *Communications of the ACM*, 5(6), 345.
3. Prim, R. C. (1957). Shortest connection networks and some generalizations. *Bell System Technical Journal*, 36(6), 1389-1401.
4. Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. *Proceedings of the American Mathematical Society*, 7(1), 48-50.
5. Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. *Canadian Journal of Mathematics*, 8(5), 399-404.
6. Edmonds, J., & Karp, R. M. (1972). Theoretical improvements in algorithmic efficiency for network flow problems. *Journal of the ACM*, 19(2), 248-264.
7. Kelley, J. E., & Walker, M. R. (1959). Critical-path planning and scheduling. *Proceedings of the Eastern Joint Computer Conference*, 160-173.
8. Euler, L. (1736). Solutio problematis ad geometriam situs pertinentis. *Commentarii Academiae Scientiarum Imperialis Petropolitanae*, 8, 128-140.
9. Kuhn, H. W. (1955). The Hungarian method for the assignment problem. *Naval Research Logistics Quarterly*, 2(1-2), 83-97.
10. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). *Introduction to Algorithms* (3rd ed.). MIT Press.
Related skills
| Skill | Stars | Updated | Works with | Status | Install |
|---|---|---|---|---|---|
| reverse-engineer-anythingmorluto/reaReverse engineer native, managed, Electron/JavaScript, packaged, firmware, and browser targets with REA, and build agent environments (AgentEnv bundles) of web applications from a live instance or a capture, and of Linux desktop apps with a task from a request. Use shipped-artifact or requested runtime evidence to explain features, compare versions, decompile code, or guide a reconstruction. Skip REA for ordinary source-repository architecture analysis. | Stars: 472k | Updated | Claude CodeCodex | Verified | Install |
| diagnosing-superpowersobra/superpowersUse when a superpowers session went wrong and your human partner wants to know why — repeated work, ignored plans, stumbles, poor results, a skill that didn't fire, "it took too long", "why is it so expensive", "what is it doing" — or wants to build a bug report for the superpowers maintainers, for the current session or a past one identified by id or path, on any harness. | Stars: 323k | Updated | Claude CodeCodex | Verified | Install |
| dispatching-parallel-agentsobra/superpowersUse when facing 2+ independent tasks that can be worked on without shared state or sequential dependencies | Stars: 323k | Updated | Claude CodeCodex | Verified | Install |
| executing-plansobra/superpowersUse when executing an implementation plan in the current session as the implementer yourself — your human partner chose inline execution, or no subagent tool is available | Stars: 323k | Updated | Claude CodeCodex | Verified | Install |