【備忘録】networkxでダイクストラ

あくまで備忘録なんで雑に記録します

AtCoderで使えそうなんで、簡単なnetworkxを使って有向グラフ
手順
matplotlibのpyplot.show()で可視化
最短の道（パス・距離）や情報の出力

AtCoderで使えそうなんで、簡単なnetworkxを使って有向グラフ

Graph：グラフ
node：頂点
edge：辺
用語degree：頂点の持つ辺の数（次数）

手順

#networkxでダイクストラ
import networkx as nx

G = nx.DiGraph()#有向グラフ
#G = nx.Graph()#無向グラフ

#頂点・辺（重み）
node_list = [1, 2, 3]
edge_weight_list = [[1, 2, 10], [2, 3, 20], [1, 3, 50]]#重み付きグラフ
#edge_list = [[1, 2], [2, 3], [1, 3]]#重み無しグラフの場合

'''単ノード・単エッジ追加したい場合
G.add_node(Edge1)
G.add_edge(Edge1, Edge2)
'''

#リスト追加
G.add_nodes_from(node_list)#頂点の追加#単品可
G.add_weighted_edges_from(edge_weight_list)#重み付き辺の追加#単品可
#G.add_edges_from(edge_list)#重み無し辺の追加#単品可

#始点・終点
start = 1
end = 3

#完成を構築
nx.draw_networkx(G)

matplotlibのpyplot.show()で可視化

最短の道（パス・距離）や情報の出力

#matplotlibで可視化
import matplotlib.pyplot as plt
plt.show()

shortest_path = nx.dijkstra_path(G, start, end)#最短パス#[1, 2, 3]
shortest_path_weight = nx.dijkstra_path_length(G, start, end)#最短パス長（重）#30

print(nx.info(G))#情報を確認
# Name:
# Type: DiGraph
# Number of nodes: 3
# Number of edges: 3
# Average in degree:   1.0000
# Average out degree:   1.0000

G.number_of_nodes()#ノードの総数
G.nodes()#ノードの要素
G.number_of_edges()#エッジの総数
G.edges()#エッジの要素