【数学建模】——【python】实现【最短路径】【最小生成树】【复杂网络分析】

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)

# 绘制节点标签
nx.draw_networkx_labels(G, pos, font_size=12, font_color='black', ax=ax)

# 绘制边标签
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='距离')

# 显示图形
plt.title(f"从城市 {start_city} 到城市 {end_city} 的最短路径图")
plt.axis('off')
plt.show()

import networkx as nx
import matplotlib.pyplot as plt

# 边列表，每个元素是一个三元组(起点 终点 权重)
edges = [
    ('A', 'B', 1),
    ('A', 'C', 4),
    ('A', 'D', 7),
    ('B', 'C', 2),
    ('B', 'D', 5),
    ('C', 'D', 3),
    ('C', 'E', 6),
    ('D', 'E', 8)
]

# 构建图
G = nx.Graph()
G.add_weighted_edges_from(edges)

# 使用Kruskal算法计算MST
mst = nx.minimum_spanning_tree(G, algorithm='kruskal')

# 绘制图
pos = nx.spring_layout(G)
plt.figure(figsize=(10, 8))

# 绘制原始图
nx.draw(G, pos, with_labels=True, node_size=500, node_color="lightblue", alpha=0.6)
labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels)

# 绘制MST
nx.draw(mst, pos, with_labels=True, node_size=500, node_color="lightgreen", edge_color="red", width=2)
labels_mst = nx.get_edge_attributes(mst, 'weight')
nx.draw_networkx_edge_labels(mst, pos, edge_labels=labels_mst)

# 计算MST的总权重
total_weight = mst.size(weight='weight')
plt.title(f"Minimum Spanning Tree (Total Weight: {total_weight})")
plt.show()

import networkx as nx
import matplotlib.pyplot as plt
from matplotlib import font_manager

# 设置中文字体
plt.rcParams['font.sans-serif'] = ['SimHei']  # 使用黑体
plt.rcParams['axes.unicode_minus'] = False  # 解决坐标轴负号显示问题

# 边列表，每个元素是一个三元组(起点, 终点, 权重)
edges = [
    ('A', 'B', 1),
    ('A', 'C', 4),
    ('A', 'D', 7),
    ('B', 'C', 2),
    ('B', 'D', 5),
    ('C', 'D', 3),
    ('C', 'E', 6),
    ('D', 'E', 8)
]

# 构建图
G = nx.Graph()
G.add_weighted_edges_from(edges)

# 使用Kruskal算法计算MST
mst = nx.minimum_spanning_tree(G, algorithm='kruskal')

# 使用Dijkstra算法计算最短路径
core_city = 'A'
lengths, paths = nx.single_source_dijkstra(mst, source=core_city)

# 绘制MST
pos = nx.spring_layout(G)
plt.figure(figsize=(20, 8))

plt.subplot(121)
nx.draw(G, pos, with_labels=True, node_size=500, node_color="lightblue", alpha=0.6)
labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels)

nx.draw(mst, pos, with_labels=True, node_size=500, node_color="lightgreen", edge_color="red", width=2)
labels_mst = nx.get_edge_attributes(mst, 'weight')
nx.draw_networkx_edge_labels(mst, pos, edge_labels=labels_mst)
total_weight = mst.size(weight='weight')
plt.title(f"最小生成树 (总权重: {total_weight})")

# 绘制最短路径图
plt.subplot(122)
nx.draw(mst, pos, with_labels=True, node_size=500, node_color="lightblue")
labels_mst = nx.get_edge_attributes(mst, 'weight')
nx.draw_networkx_edge_labels(mst, pos, edge_labels=labels_mst)

for target in lengths:
    if target == core_city:
        continue
    path = paths[target]
    edges_in_path = [(path[i], path[i + 1]) for i in range(len(path) - 1)]
    nx.draw_networkx_edges(mst, pos, edgelist=edges_in_path, width=2, edge_color='r')
    path_length = lengths[target]
    plt.text(pos[path[-1]][0], pos[path[-1]][1], f"{path_length:.2f}", fontsize=12, color='red')

plt.title(f"从核心城市 {core_city} 出发的最短路径")

plt.show()