問題

ソースコード

ダイクストラ法で解けそうであるが、頂点Aから、どこかにいき再び頂点Aに戻ってくる経路は閉路なためそのままではダイクストラ法やワーシャルフロイド法は使えない。よって以下のように一度頂点Aから頂点Bまでの経路の最短距離を求めるように問題を変換する。

１．「頂点1に隣接する辺を除いたグラフ」の全点対の最短経路を前計算しておく

２．頂点1に隣接する頂点のうちどの2つを閉路に含めるか全通り試す

３．前計算した最短経路の結果と合わせて最短閉路の長さを求める

初めのステップの「「頂点1に隣接する辺を除いたグラフ」の全点対の最短経路を前計算しておく」という処理にワーシャル・フロイド法を用いる。

ワーシャル・フロイド法とは、グラフにおいて、全ての頂点間の最短距離を算出するための方法である。計算量は頂点の数をVとするとO(V²)となる。仕組みは以下のようになる。