あくまで備忘録なんで雑に記録します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()#エッジの要素
コメント