目录

1. 最短路径问题 - 绘制城市间旅行最短路径图

题目描述：

要求：

示例数据：

python 代码实现

实现思想：

要点：

2. 最小生成树问题 - Kruskal算法绘制MST

题目描述：

要求：

示例数据：

python代码实现

实现思想：

要点：

3. 结合最短路径与最小生成树的复杂网络分析

题目描述：

python代码

实现思想： 

要点：

总结三个问题

专栏：数学建模学习笔记

上一篇：【数学建模】图与网络模型的学习

本篇是题目练习

1. 最短路径问题 - 绘制城市间旅行最短路径图

题目描述：

假设有一个包含多个城市及其之间距离的列表（或图结构），其中每个城市是图中的一个节点，城市之间的距离是边的权重。使用Dijkstra算法或Floyd-Warshall算法（视情况而定，如果图中节点数较多，推荐使用Dijkstra；如果需要求出所有点对间的最短路径，则使用Floyd-Warshall）来计算并绘制出从一个指定城市到其他所有城市的最短路径图。

要求：

（1）使用Python编程，可以利用networkx库来构建图和处理图算法。

（2）绘制结果应包含所有节点（城市）和表示最短路径的边，边的粗细或颜色可以表示距离长短。

（3）标注每条边的权重（距离）。

（4）城市的数量N通过键盘输入，城市之间的距离通过随机数生成。

示例数据：

# 城市间的距离矩阵（假设为完全图，即任意两城市间都有直接路径）  

distances = [  

    [0, 5, 10, 15],  

    [5, 0, 3, 8],  

    [10, 3, 0, 6],  

    [15, 8, 6, 0]  

]  

# 假设城市名称为 A, B, C, D

python 代码实现

<code>import networkx as nx

import matplotlib.pyplot as plt

import numpy as np

import matplotlib.font_manager as fm

# 设置中文字体

plt.rcParams['font.sans-serif'] = ['SimHei'] # 使用黑体

plt.rcParams['axes.unicode_minus'] = False # 解决负号显示问题

# 输入城市数量

N = int(input("请输入城市数量: "))

# 生成随机的距离矩阵，距离在1到20之间

distances = np.random.randint(1, 21, size=(N, N))

np.fill_diagonal(distances, 0) # 对角线距离为0

# 打印生成的距离矩阵

print("城市间的距离矩阵：")

print(distances)

# 创建图并添加边

G = nx.Graph()

# 添加节点

cities = [chr(i) for i in range(65, 65 + N)] # 使用A, B, C...表示城市

G.add_nodes_from(cities)

# 添加边及其权重

for i in range(N):

for j in range(i + 1, N):

G.add_edge(cities[i], cities[j], weight=distances[i][j])

# 输入起始城市

start_city = input(f"请输入起始城市({', '.join(cities)}): ")

# 使用Dijkstra算法计算从起始城市到所有其他城市的最短路径

lengths, paths = nx.single_source_dijkstra(G, source=start_city)

# 打印最短路径信息

print("从起始城市到其他城市的最短路径：")

for target in cities:

print(f"{start_city}到{target}的最短路径为{paths[target]}，距离为{lengths[target]}")

# 获取从起始城市到最后一个城市的最短路径

end_city = cities[-1]

shortest_path = paths[end_city]

# 绘制图形

pos = nx.spring_layout(G)

# 创建绘图区域

fig, ax = plt.subplots()

# 绘制所有节点

nx.draw_networkx_nodes(G, pos, node_size=500, ax=ax)

# 绘制所有边并根据权重调整颜色和宽度

edges = G.edges(data=True)

edge_colors = [edge[2]['weight'] for edge in edges]

edge_widths = [edge[2]['weight'] / 5 for edge in edges]

edges_drawn = nx.draw_networkx_edges(G, pos, edgelist=edges, width=edge_widths, edge_color=edge_colors, edge_cmap=plt.cm.Blues, ax=ax)

# 绘制最短路径的边，使用不同颜色和宽度

path_edges = [(shortest_path[i], shortest_path[i + 1]) for i in range(len(shortest_path) - 1)]

nx.draw_networkx_edges(G, pos, edgelist=path_edges, width=2, edge_color='r', ax=ax)code>

# 绘制节点标签

nx.draw_networkx_labels(G, pos, font_size=12, font_color='black', ax=ax)code>

# 绘制边标签

edge_labels = {(edge[0], edge[1]): edge[2]['weight'] for edge in edges}

nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, ax=ax)

# 创建颜色映射条

sm = plt.cm.ScalarMappable(cmap=plt.cm.Blues, norm=plt.Normalize(vmin=min(edge_colors), vmax=max(edge_colors)))

sm.set_array([]) # 仅用于显示色条

fig.colorbar(sm, ax=ax, label='距离')code>

# 显示图形

plt.title(f"从城市 {start_city} 到城市 {end_city} 的最短路径图")

plt.axis('off')

plt.show()

请输入城市数量: 5

城市间的距离矩阵：

[[ 0  3  6  1 16]

 [18  0  9 11  3]

 [16  2  0  5 11]

 [ 9  8  1  0 17]

 [ 2  7  1  3  0]]

请输入起始城市(A, B, C, D, E): A

从起始城市到其他城市的最短路径：

A到A的最短路径为['A']，距离为0

A到B的最短路径为['A', 'B']，距离为3

A到C的最短路径为['A', 'C']，距离为6

A到D的最短路径为['A', 'D']，距离为1

A到E的最短路径为['A', 'B', 'E']，距离为6