当前位置: 首页> 汽车> 维修 > 【图论应用】使用多路图(multigraph)对上海地铁站点图建模,并解决最短路径问题

【图论应用】使用多路图(multigraph)对上海地铁站点图建模,并解决最短路径问题

时间:2025/7/11 7:51:05来源:https://blog.csdn.net/takedachia/article/details/139573268 浏览次数: 0次

文章目录

    • 1 前言
    • 2 导包+导入数据集
    • 3 创建多路图,导入节点和边信息
    • 3 绘制线路图
    • 4 计算最短路径

1 前言

最近正在学习图神经网络,先pick up了一些最基础的图论知识并学习了一些好玩的应用。

本文启发于B站视频(BV1LY411R7HJ),其对于上海地铁站点图使用了无向图也就是nx.Graph()进行建模的(Python的NetworkX库)。但是由于上海地铁存在两个站点之间可有多条线路相通的情况(如3号线和4号线共享了“虹桥路 ”、“延安西路”、“中山公园”、“金沙江路”、“曹杨路”等多个站点),所以单纯的无向图严格来说不能充分解决该问题。

所以准确来讲,应该建立一个多路图(multigraph),即节点与节点之间应可以创建多条边。下图是多路图(左)与普通图(右)之间的区别。
在这里插入图片描述
在NetworkX库中,nx.Graph()的add_edges_from()方法是无法添加多条边的,文档里是这样记载的:

Notes-----Adding the same edge twice has no effect but any edge datawill be updated when each duplicate edge is added.

下面解决这个问题:

2 导包+导入数据集

import networkx as nx
import pandas as pd
import matplotlib.pyplot as plt
import matplotlib.colors as mcolors
%matplotlib inlineplt.rcParams['font.sans-serif']=['SimHei']  # 用来正常显示中文标签
plt.rcParams['axes.unicode_minus']=False  # 用来正常显示负号# 上海地铁站点连接表
df = pd.read_csv('shanghai_subway.csv')
df.head()

在这里插入图片描述

3 创建多路图,导入节点和边信息

# 创建多路图
G = nx.MultiGraph()for idx, row in df.iterrows(): # 遍历表格的每一行,添加节点G.add_edges_from([(row['前一站'], row['后一站'])], line=row['地铁线'], time=row['时间(分钟)'])print(f'节点个数:{len(G)},连接个数:{len(G.edges)}')# 查看连接属性特征
print(G.edges(data=True))# 查看连接属性特征(multigraph)
# 最后一个维度为边的index,可能为 0,1,2...
print(G.edges[('同济大学', '四平路', 0)])# 查看两个节点之间的边
print(G['上海火车站']['中潭路'])

在这里插入图片描述
可以看到查看 G[‘上海火车站’][‘中潭路’] 可以看到所有连接两节点之间的边信息

3 绘制线路图

# 节点排版布局-默认弹簧布局
pos = nx.spring_layout(G, seed=123)# 设置其它可视化样式
options = {"font_size": 6,"node_size": 300,"node_color": "white","edgecolors": "black","linewidths": 1, # 节点线宽"width": 2, # edge线宽
}
plt.figure(figsize=(15,15))
nx.draw_networkx(G, pos, **options)

在这里插入图片描述

4 计算最短路径

下面计算昌吉东路到同济大学的最短路径

# 任意两节点之间是否存在路径
print(nx.has_path(G, source='昌吉东路', target='同济大学'))# 任意两节点之间的最短路径
print(nx.shortest_path(G, source='昌吉东路', target='同济大学', weight='time'))# 任意两节点之间的最短路径长度
print(nx.shortest_path_length(G, source='昌吉东路', target='同济大学', weight='time'))

在这里插入图片描述

# 指定起始站和终点站
A_station = '昌吉东路'
B_station = '同济大学'# 计算最短路径的节点序列
shortest_path = nx.shortest_path(G, source=A_station, target=B_station, weight='time')# 计算最短路径长度
shortest_path_length = nx.shortest_path_length(G, source=A_station, target=B_station, weight='time')# 找出最短路径经过的边
edges_in_path = []
for i in range(len(shortest_path) - 1):u = shortest_path[i]v = shortest_path[i + 1]# 找到具有最小权重的边min_weight = float('inf')min_edge = Nonefor key, data in G[u][v].items():if data['time'] < min_weight:min_weight = data['time']line_id = data['line'] # 地铁线编号min_edge = (u, v, line_id, data['time'])edges_in_path.append(min_edge)print(f"Shortest path from {A_station} to {B_station}: {shortest_path}")
print(f"Shortest path length from {A_station} to {B_station}: {shortest_path_length}")

在这里插入图片描述

print('Edges in the shortest path: ')
for i in edges_in_path:print(f"{i[0]}--->{i[1]} {i[2]}号线 {i[3]}分钟")

在这里插入图片描述
到此解决!

我们还可以看到这里算出的从昌吉东路到同济大学的所用时间为58分钟,但原视频是59分钟。这是因为从“上海火车站”到“宝山路”两个节点的两条边所用 time 不同:
在这里插入图片描述所以如果直接使用Graph的add_edges_from方法,会把3号线的信息被覆盖成4号线,就会失去3号线那段共享路线的信息,导致路径计算出现差错。


本文代码:https://github.com/aquamarineaqua/D2L-My-Note/blob/main/Graph-Neural-Network/C5_topost.ipynb

关键字:【图论应用】使用多路图(multigraph)对上海地铁站点图建模,并解决最短路径问题

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: