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

文章目录

- 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 inline

plt.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 = None
    for 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号线那段共享路线的信息，导致路径计算出现差错。