を参照していく。
前回
6. グラフ構造
ヒトのつながりを表現する手段であるグラフ理論に基づくグラフ構造が利用し得る。
6.5 最短距離を求める
6.5.4 すべての頂点間の最短距離
すべての頂点間の最短距離が欲しい場合、ダイクストラ法をすべての頂点に適用する方法では計算量が多くなる場合がある。実際、頂点の数を辺の数をとすれば、計算量はになる。グラフに辺が密にあれば更にになってしまう。
法を用いれば計算量で計算が可能になる。ただし辺の密度が低ければダイクストラ法の方が速い。法は動的計画法の一種である。
6.5.5 動的計画法
頂点からへの道と、その途中にある頂点が現在の最短経路だったとする。もし途中のを結ぶより短い道があるならば、そちらがからへの最短経路の一部として選ばれるはずである。このように税体が最適化されているときに局所も最適化されていることを最適化の原理という。この性質を利用したアルゴリズムを設計する方法を動的計画法という。
6.5.6 Floyd-Warshall法
まず個あるすべての頂点ペアについて初期状態を設定する。ある頂点ペアが1つの辺で結ばれているならばそれは2点間の最短距離になる。もし隣接していなければ距離を無限大とする。自分へのループは無いと仮定する。この状態である1つの頂点を考える。隣接していない頂点ペアがを介してつながっていればそれは最短距離になる。これを帰納的に考え、番目まで来たとする。を番目までの頂点だけを考慮に入れているときのの最短距離だとする。番目の頂点を考慮したとき、は
で求めることができる。これは番目の頂点が考慮すべき対象に加わった時に、そこを通るべきか否かを判定している。新たに加えた番目の頂点を通った方が近いならば最短距離を更新する。
6.5.7 Floyd-Warshall法のサンプル
######################## ### Floyd-Warshall法 ### ######################## import math import random # グラフの生成 def generate_graph(n, m): """ n個の頂点とm個の辺の持つグラフを作成する """ graph_data = [[0] * n for i in range(n)] edge_set = set() while len(edge_set) < m: i, j = random.sample(range(n), 2) if i > j:i, j = j, i edge_set.add((i,j)) graph_data[i][j] = graph_data[j][i] = 1 return graph_data, edge_set # テストデータを生成 random.seed(6) node_num = 16 edge_num = 20 my_graph, edge_set = generate_graph(node_num, edge_num) def all_pairs_shortest_paths(W): # 頂点の数 n = len(W) # 結果を格納する行列を準備する res = [[0] * n for i in range(n)] # 用意した行列を初期化する for i in range(n): for j in range(i,n): if i == j: val = 0 elif W[i][j]: val = W[i][j] else: val = math.inf res[i][j] = res[j][i] = val # 動的計画法で前兆転換の最短距離を求める for k in range(n): for u in range(n): for v in range(n): res[u][v] = min(res[u][v], res[u][k] + res[k][v]) return res all_pairs_shortest_paths(my_graph)