NetworkXで経路探索をやってみる。（グラフ作成〜A*アルゴリズム） - Qiita

はじめに グラフ理論を学ぶ機会が、増えてきました。 ある出発地点から、目的地点までの経路を考える時にも、グラフ理論が活用できます。 Pythonでは、NetworkXという、グラフ計算ライブラリがあります。 本記事は、NetworkXを使用して、グラフの作成〜経路探索してみました。 今回やりたいことは、３つ。 格子状にノードを配置した、グラフを作成する（下図、左） グラフから、ランダムにノードを削除する（下図、中央） A*アルゴリズムを使用して、経路探索する（下図、右） コードを書いていく Step0. 準備 Python 3.8.6、NetworkX 2.6.2を使います。 まず、importしていく。 def make_graph(n, m):# n*mの格子状のグラフ作成 G = nx.Graph() # n*m個、ノードを追加する for i in range(n): for j