基于Python+Networkx的最短路径

最短路径"/>

基于Python+Networkx的最短路径

networkx是一个用Python语言开发的图论与复杂网络建模工具，内置了常用的图与复杂网络分析算法，可以方便的进行复杂网络数据分析、仿真建模等工作。利用networkx可以以标准化和非标准化的数据格式存储网络、生成多种随机网络和经典网络、分析网络结构、建立网络模型、设计新的网络算法、进行网络绘制等。

networkx支持创建简单无向图、有向图和多重图（multigraph）；内置许多标准的图论算法，节点可为任意数据；支持任意的边值维度，功能丰富，简单易用。networkx以图（graph）为基本数据结构。图既可以由程序生成，也可以来自在线数据源，还可以从文件与数据库中读取。

使用方法：
　　1. 导入networkx，matplotlib包
　　2. 建立网络
　　3. 绘制网络 nx.draw()
　　4. 建立布局 pos = nx.spring_layout美化作用

导入networkx，matplotlib包

import matplotlib.pyplot as plt  # 导入 Matplotlib 工具包
import networkx as nx  # 导入 NetworkX 工具包
from typing import List

使用networkx画图

# 初始化空的无向图
graph = nx.Graph()  

# 向图中添加多条赋权边: (node1,node2,weight)
graph.add_weighted_edges_from([(1, 2, 50),(1, 3, 60),(2, 4, 65),(2, 5, 40),(3, 4, 52),(3, 7, 45),(4, 5, 50),(4, 6, 30),(4, 7, 42),(5, 6, 70)]
)  

# 指定顶点位置
coordinates = {1: (2.5, 10),2: (0, 5),3: (7.5, 10),4: (5, 5),5: (2.5, 0),6: (7.5, 0),7: (10, 5)
}  

# 绘制无向图
# alpha：节点透明度
# node_color：节点颜色
# with_labels: 节点标签
nx.draw_networkx(graph, coordinates, with_labels=True, alpha=1)  

深度优先搜索遍历图

tree = nx.dfs_tree(graph, source=1, )
tree.nodes, tree.edges

(NodeView((1, 2, 4, 3, 7, 5, 6)),OutEdgeView([(1, 2), (2, 4), (4, 3), (4, 5), (3, 7), (5, 6)]))

# 画dfs_tree
nx.draw_networkx(graph, coordinates, with_labels=True, alpha=1)  # 绘制无向图
labels = nx.get_edge_attributes(graph, 'weight')  # 获取边的权值
nx.draw_networkx_edges(graph, coordinates, edgelist=tree.edges, edge_color='r', width=2)  # 设置指定边的颜色
nx.draw_networkx_edge_labels(graph, coordinates, edge_labels=labels)  # 显示边的权值
plt.show()

dijkstra算法寻找最短路

# node1->node6的最短路径为：
path:List = nx.dijkstra_path(graph, 1, 6)
path

[1, 3, 4, 6]

# 无向图，判断两点之间是否存在路径
nx.has_path(graph, 1, 6)

True