Python学習

Pythonnetworkxモジュールがダイクストラの最短経路を見つける



Python Networkx Module Find Dijkstra Shortest Path



a）networkxの概要：これは主に、複雑なネットワークを作成および運用し、複雑なネットワークの構造、ダイナミクス、および機能を学習するために使用されます。これは、ネットワーク構造の分析、ネットワークモデルの確立、新しいネットワークアルゴリズムの設計、ネットワークの描画などに使用されます。 networkxをインストールして確認してください 公式サイト
networkxの基本操作を参照してください
networkx
Pythonグラフ理論パッケージネットワーク（最短パス、パッケージ付きの最小スパニングツリー）

例は次のとおりです

図に示すように、次のノード間の最短距離を確認してください
画像
コードの実装



import networkx as nx import matplotlib.pyplot as plt import numpy as np #Define the number of nodes nodes=np.array(['v1','v2','v3','v4','v5']) #Define the distance between nodes row=np.array(['v1','v1','v1','v2','v2','v2','v3','v3','v3','v3','v4','v4','v4','v5','v5','v5']) col=np.array(['v2','v3','v4','v1','v3','v5','v1','v2','v4','v5','v1','v3','v5','v3','v4','v2']) value=np.array([2,1,4,2,6,3,1,6,3,8,4,3,7,8,7,3]) #Generate undirected graph G=nx.Graph() #Add a node to the graph for i in range(0,np.size(nodes)): G.add_node(nodes[i]) #Add weighted edges for i in range(0,np.size(row)): G.add_weighted_edges_from([(row[i],col[i],value[i])]) #Set network layout pos=nx.shell_layout(G) #Draw a network image nx.draw(G,pos,with_labels=True, node_color='white', edge_color='b', node_size=800, alpha=0.5) # plt.ion() # Turn on interactive mode # plt.title('slfe_Net') # plt.ioff() # plt.show() edge_labels = nx.get_edge_attributes(G,'weight') nx.draw_networkx_edge_labels(G, pos, edge_labels) plt.draw() plt.pause(1)# Interval seconds: 3s plt.close() ''' Shortest Path with dijkstra_path ''' #dijkstra method to find the shortest path start,end=input('Please enter the start and end nodes separated by spaces:').split() path=nx.dijkstra_path(G, source=start, target=end) print('Path from node {0} to {1}:'.format(start,end), path) distance=nx.dijkstra_path_length(G, source=start, target=end) print('The distance from node {0} to {1} is:'.format(start,end), distance)

手順の説明 ：このコードは、matplotlibの描画とnumpyに適用されて行列を作成します
運用結果
画像
画像
OKご清聴ありがとうございました。