安徽黄山网站建设,移动网站系统,响应式网站代理,做网站用到哪些软件文章目录 1.构建图2.使用networkX查找最短路径3.自己构建方法 教程仓库地址#xff1a;github networkx_tutorial import networkx as nx
import matplotlib.pyplot as plt1.构建图
# 创建有向图
G nx.DiGraph()# 添加带权重的边
edges [(0, 1, 1), (0, 2, 2), (1, 2, 1), … 文章目录 1.构建图2.使用networkX查找最短路径3.自己构建方法 教程仓库地址github networkx_tutorial import networkx as nx
import matplotlib.pyplot as plt1.构建图
# 创建有向图
G nx.DiGraph()# 添加带权重的边
edges [(0, 1, 1), (0, 2, 2), (1, 2, 1), (1, 3, 2), (2, 3, 1),(3, 4, 3), (2, 4, 4), (4, 5, 2), (3, 5, 5),
]
G.add_weighted_edges_from(edges)# 绘制图
pos nx.spring_layout(G) # 使用Spring布局
nx.draw(G, pos, with_labelsTrue, node_size2000, node_colorlightblue, font_size10)
nx.draw_networkx_edge_labels(G, pos, edge_labels{(u, v): G[u][v][weight] for u, v in G.edges()}, font_colorred)# 显示图
plt.show()
2.使用networkX查找最短路径
from itertools import islice
def k_shortest_paths(G, source, target, k, weightNone):return list(islice(nx.shortest_simple_paths(G, source, target, weightweight), k))# 获取 k-最短路径
paths k_shortest_paths(G, 0, 5, 3, weight)# 输出路径和权重
for i, path in enumerate(paths):weight sum(G[path[n]][path[n 1]][weight] for n in range(len(path) - 1))print(fPath {i 1}: {path}, weight: {weight})
Path 1: [0, 1, 3, 5], weight: 8
Path 2: [0, 2, 3, 5], weight: 8
Path 3: [0, 1, 2, 3, 5], weight: 83.自己构建方法
from itertools import count
from heapq import heappush, heappop
import networkx as nx
import pandas as pd
import matplotlib.pyplot as pltclass K_shortest_path(object):def __init__(self,G, k3, weightweight) - None:self.G G self.k kself.weight weightself.G_original Gdef get_path_length(self,G,path:list, weightweight):计算每条路径的总阻抗基于weightArgs:G (nx.graph): 构建的图path (list): 路径weight (str, optional): 边的权重计算基于什么可以是时间也可以是距离. Defaults to weight.length 0if len(path) 1:for i in range(len(path) - 1):u path[i]v path[i 1]length G.edges[u,v].get(weight, 1)return length def find_sp(self,s,t,G):找到第一条P(1)Args:s (node): 路径起点t (node): 路径终点lenght:P(1)对应的长度path:P(1)对应的路径 listpath_1 nx.shortest_path(GG,sources,targett,weightself.weight)length_1 nx.shortest_path_length(GG,sources,targett,weightself.weight)# length_1, path_1 nx.single_source_dijkstra(G,sources,weightweight)return length_1, path_1def find_Pi_sp(self,source,target):if source target:return ([0], [[source]]) G self.Gk self.klength, path self.find_sp(GG,ssource,ttarget)lengths []paths []lengths.append(length)paths.append(path)c count() B [] G_original self.G.copy() for i in range(1, k):for j in range(len(paths[-1]) - 1): spur_node paths[-1][j]root_path paths[-1][:j 1]edges_removed []for c_path in paths:if len(c_path) j and root_path c_path[:j 1]:u c_path[j] #节点v c_path[j 1] #节点if G.has_edge(u, v): #查看uv节点之间是否有路径edge_attr G.edges[u,v][weight]G.remove_edge(u, v) #移除边edges_removed.append((u, v, edge_attr))for n in range(len(root_path) - 1):node root_path[n]# out-edgesdict_d []for (u,v,edge_attr) in G.edges(nbunch node,data True ):# for u, v, edge_attr in G.edges_iter(node, dataTrue):edge_attr edge_attr[weight]dict_d.append((u,v))edges_removed.append((u, v, edge_attr))G.remove_edges_from(dict_d) if G.is_directed():# in-edgesin_edges_d_list []for (u,v,edge_attr) in G.edges(nbunch node,data True ):# for u, v, edge_attr in G.in_edges_iter(node, dataTrue):# edge_attr edge_attr[weight]edge_attr G.edges[u,v][weight]# G.remove_edge(u, v)in_edges_d_list.append((u,v))edges_removed.append((u, v, edge_attr))G.remove_edges_from(in_edges_d_list) spur_path_length, spur_path nx.single_source_dijkstra(G, spur_node, weightself.weight) if target in spur_path and spur_path[target]:total_path root_path[:-1] spur_path[target]total_path_length self.get_path_length(G_original, root_path, self.weight) spur_path_length[target] heappush(B, (total_path_length, next(c), total_path))for e in edges_removed:u, v, edge_attr eG.add_edge(u, v, weight edge_attr)if B:(l, _, p) heappop(B) lengths.append(l)paths.append(p)else:breakreturn (lengths,paths) if __name__ __main__:# 创建有向图G nx.DiGraph()# 添加带权重的边edges [(0, 1, 1), (0, 2, 2), (1, 2, 1), (1, 3, 2), (2, 3, 1),(3, 4, 3), (2, 4, 4), (4, 5, 2), (3, 5, 5), ]G.add_weighted_edges_from(edges)for u, v, weight in edges:G.add_edge(u, v, weightweight)KSP K_shortest_path(GG,k3,weightweight)KSP.G# 绘制图pos nx.spring_layout(KSP.G) # 使用Spring布局nx.draw(KSP.G, pos, with_labelsTrue, node_size2000, node_colorlightblue, font_size10)nx.draw_networkx_edge_labels(KSP.G, pos, edge_labels{(u, v): KSP.G[u][v][weight] for u, v in KSP.G.edges()}, font_colorred)# 显示图plt.show()# 最短路径查询source 0target 5(lengths,paths) KSP.find_Pi_sp(sourcesource,targettarget)k_df pd.DataFrame((lengths,paths)).Tk_df.columns [weight,path]print(k_df) weight path
0 8 [0, 1, 3, 5]
1 8 [0, 2, 3, 5]
2 8 [0, 1, 2, 3, 5]
