Pythonで最短距離を求める

方法を

じっくり理解するグラフ理論・ネットワーク分析の仕組みの解説とハンズオン
https://liberal-arts-beginners.connpass.com/event/149327/

で教わってきたので、成果披露。

networkxを使う。こんなかんじ

##########################################
#   例
##########################################
G=nx.DiGraph()

#各ノード、エッジ定義（距離と価格２つの値を持てる）
G.add_edge(1,2,distance=100,cost=100)
G.add_edge(2,3,distance=150,cost=100)
G.add_edge(1,3,distance=220,cost=300)

#グラフを書く
nx.draw_networkx(G)
plt.show()

#距離で最短を求める
result=nx.shortest_path(G,1,weight='distance')
print(result)

#運賃が最安値を求める
resultnx.shortest_path(G,1,weight='cost')
print(result)

結果はこんなかんじ


なお、講義ではやってなかったけど、
最短距離はダイクストラ法が有名。ダイクストラ法の場合は
shortest_pathの代わりに

all_pairs_dijkstra_path_length
とかを用いる。

https://showa-yojyo.github.io/notebook/python-networkx/shortest-path.html


参照。dijkstra_path(G, source, target[, weight])とかの使い方は
Shortest Paths
https://networkx.github.io/documentation/networkx-2.2/reference/algorithms/shortest_paths.html

にある。