グラフを使った最適化¶
以降で、NetworkXはimport networkx as nx
として使い、nx
として参照します。
最短路問題¶
最短路問題とは
グラフの各辺が距離をもつとき、始点から終点への路の中で最も距離の和の小さいものを求める問題
参考:最短経路問題
最短路を求める関数(nx.dijkstra_path
)¶
第1引数:グラフオブジェクト
第2引数:始点
第3引数:終点
返り値:最短路(頂点のリスト)
最短路の距離を求める関数(nx.dijkstra_path_length
)¶
第1引数:グラフオブジェクト
第2引数:始点
第3引数:終点
返り値:最短路の距離
最短路を求めるアルゴリズム¶
最短路は、ダイクストラ法というアルゴリズムで求められます。
始点から仮の距離を更新していく方法で、厳密に最適な解を求められます。
要点は以下のようになります。
各頂点の、
始点からの仮距離
を∞とします。始点の、
始点からの仮距離
を0とします。未探索の頂点集合
を全ての頂点の集合とします。未探索の頂点集合
が空でない間、下記を繰り返します。未探索の頂点集合
の中で始点からの仮距離
が最小の頂点をv
とし、未探索の頂点集合
からv
を除きます。v
に接続する頂点に対し、始点からの仮距離
を更新します。
参考