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