はじめに
- 最近、グラフ理論の最小経路について2つほど投稿した。
- でも、頂点aと頂点bの最短距離は取得していたものの、a〜b間の経路自体(頂点a⇒頂点□⇒頂点△⇒頂点b)をデータ取得していなかったと気付いて、追加で取得方法を勉強した。まぁ、実際に書いてみたら難しい話では無かったけどね。
- また、ダイクストラ法では、頂点aを指定した後、全ての頂点との最短距離を取得していたけど、全ての2頂点間の距離を一度に取得する方法を知ったので、ついでに紹介する。
ワーシャルフロイド法(全ての2頂点間の距離を一度に取得する方法)
- 詳しいことはwikiを読んで欲しい。
- でも正直、文章で書かれた説明を読むより、コードを読んだ方が分かり易いんじゃ無いかな?ちなみに、頂点番号については、競技プログラミング等では、1から始まる順番だけど、配列に格納して利用する関係から、コード上では頂点番号を0から始まる順番に変換(1を引く)して、最後の出力の際に、元に戻す(1を足す)ことをしている。
let (N,M) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]
let INF:UInt64 = 999 // 十分に大きな数値
// 2点間の重みを格納するd[N(出発点)×N(到着点)の二次元配列]。後ほど、ワーシャルフロイド法で、より小さい数値に塗り替えていく
var d = [[UInt64]](repeating:[UInt64](repeating:INF,count:N),count:N)
for _ in 0..<M {
let (a,b,w) = [readLine()!.split(separator:" ").map{UInt64($0)!}].map{(Int($0[0])-1,Int($0[1])-1,$0[2])}[0]
d[a][b] = w
d[b][a] = w // 無向辺の場合
}
for v in 0..<N {
d[v][v] = 0 // 当然、同じ点間の重みはゼロとする
}
// ワーシャルフロイド法適用前の d -- 下記㋐
// ワーシャルフロイド法
for k in 0..<N { //経由点
for i in 0..<N { //スタート地点
for j in 0..<N { //ゴール地点
d[i][j] = min( d[i][j] , d[i][k] + d[k][j] )
// 経由点kを1つずつ増やしていき、そのつど、全ての頂点間(i〜j)の最短距離を塗り替える
}
}
}
// ワーシャルフロイド法適用後の d -- 下記㋑
- ワーシャルフロイド法は、経由点kを一つずつ増やしていき、都度、全ての頂点i,頂点j間の最短距離を塗り替えることを行う。よって、この手法では、計算量が$O(V^3)$になり、Vが1000程度になると、計算量が$10^8$を超えてしまい、競技プログラミングの制約を超える。
- 入力例は、下記のグラフを前提としたものを用意した。
6 9 // 頂点6個、辺9本
1 2 7 //辺①:頂点1と頂点2を結ぶ重み7の辺
1 3 9
1 6 14
2 3 10
2 4 15
3 4 11
6 3 2
6 5 9
4 5 6
- ㋐ワーシャルフロイド法適用前のd[N(出発点)×N(到着点)の二次元配列]。下記で数値が999以外のものは、頂点間に辺があることを意味する。数値は重み。
0 7 9 999 999 14 // 頂点1から{頂点1,頂点2,...,頂点6}への辺の重み
7 0 10 15 999 999 // 頂点2から{頂点1,頂点2,...,頂点6}への辺の重み
9 10 0 11 999 2
999 15 11 0 6 999
999 999 999 6 0 9
14 999 2 999 9 0
- ㋑ワーシャルフロイド法適用後のd。下記で数値が999以外のものは、頂点間に経路があることを意味する。数値は最短距離。繰り返しになるけど、全ての頂点間の最短距離を算出できるのが、ワーシャルフロイド法の特徴。
0 7 9 20 20 11 // 頂点1から{頂点1,頂点2,...,頂点6}への最短距離
7 0 10 15 21 12 // 頂点2から{頂点1,頂点2,...,頂点6}への最短距離
9 10 0 11 11 2
20 15 11 0 6 13
20 21 11 6 0 9
11 12 2 13 9 0
経路履歴を追加(ワーシャルフロイド法の場合)
- 上記のワーシャルフロイド法に、経路履歴をログする機能を付ける。
- そのまえに、前記のワーシャルフロイド法は、わかりやすさ重視で、INFとして999を使っちゃうようなだらしねぇコードなので、下記の通り、リファクタリングした。
let (N,M) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]
var d = [[UInt64?]](repeating:[UInt64?](repeating:nil,count:N),count:N)
for _ in 0..<M {
let (a,b,w) = [readLine()!.split(separator:" ").map{UInt64($0)!}].map{(Int($0[0])-1,Int($0[1])-1,$0[2])}[0]
d[a][b] = w
d[b][a] = w // 無向辺の場合
}
for v in 0..<N {
d[v][v] = 0
}
///////////////////////////////
// 後で、経由地情報の配列を挿入㋐ //
///////////////////////////////
// フロイドワーシャル法
for k in 0..<N { //経由点
for i in 0..<N { //スタート地点
for j in 0..<N { //ゴール地点
// k in 0..<(k-1)でiから通ったことがある、もしくはi⇒kが辺で結ばれている時に通過
guard let d_ik = d[i][k] else {continue}
// k in 0..<(k-1)でjまで通ったことがある、もしくはk⇒jが辺で結ばれている時に通過
guard let d_kj = d[k][j] else {continue}
// k経由でi⇒jが通じていても、最短距離を更新できなければスキップ
if let d_ij = d[i][j] {
if d_ij <= d_ik + d_kj {continue}
}
// より短いルートが存在するときのみここまで、辿り着く
d[i][j] = d_ik + d_kj
///////////////////////////////
// 後で、経由地情報の更新を挿入㋑ //
///////////////////////////////
}
}
}
- 上記のコードに、経由地情報を追加するため、下記のコードを追加する。
///////////////////////////////
// ㋐経由地情報の配列 //
///////////////////////////////
var via = [[Int]](repeating:[Int](repeating:0,count:N),count:N)
for i in 0..<N {
for j in 0..<N {
via[i][j] = i
}
}
///////////////////////////////
// ㋑経由地情報の更新 //
///////////////////////////////
via[i][j] = via[k][j]
- 前記の入力例(頂点数6個)における、経由地情報の配列viaの初期状態は以下の通り。なお、viaで、頂点番号は1〜6ではなく、0〜5で表現される。紛らわしいので、例えば頂点番号1は頂点番号[0]と表現する。
0 0 0 0 0 0
1 1 1 1 1 1
2 2 2 2 2 2
3 3 3 3 3 3
4 4 4 4 4 4
5 5 5 5 5 5
- フロイドワーシャル法適用後のviaは以下の通り。下記の数値は、"最終"の経由地を表す。例えば、入力例のgifを見れば分かるとおり、頂点1と頂点5の最短経路は1⇒3⇒6⇒5であり、via上の1を減じた数値で表現すれば、[0]⇒[2]⇒[5]⇒[4]となる。下記viaの(i:0,j:4)の位置にある5は、左記の赤字の5であり、最終の経由地を表している。
0 0 0 2 5 2 // 5は ( i[出発]= 0 , j[到着]= 4 )のマトリックスの位置にある
1 1 1 1 3 2
2 2 2 2 5 2
2 3 3 3 3 2
2 3 5 4 4 4
2 2 5 2 5 5
- 上記のviaを元に全ての経由地を配列化する関数route(出発地,到着地)を作ると以下の通り
func route(_ start:Int,_ goal:Int)->[Int]{
var s = start - 1
var g = goal - 1
if d[s][g] == nil {return [-1]}
var temp = g
var ans = [goal] //頂点番号へ
while temp != s {
let next = via[s][temp]
ans.append(next + 1) // 0スタートのindexから1スタートの頂点番号へ
temp = next
}
ans.reverse()
return ans
}
// gifアニメのグラフを入力例としたとき
print(route(1,5)) // [1, 3, 6, 5]
print(route(1,6)) // [1, 3, 6]
経路履歴を追加(ダイクストラ法の場合)
- 過去にダイクストラ法(ヒープ化前)でコードを書いたときも経路情報を取得して無かったので、これも追加してみる。
- ダイクストラ法では、スタート地点を固定した上で、全ての頂点{i=0,2,3,...,N-1}への最短距離を算出するが、各頂点に対し下記の配列を用意した。
- seen[i]:Bool 頂点iを調査済みか同課のフラグ
- d[i]:UInt64 頂点iまでの最短距離
- 今回、更に下記の配列viaを追加することとなる。当然、上記の配列dが更新されるのと同じタイミングで、viaを更新することとなる。
- via[i]:Int 頂点iまでの最短距離を実現するとき、最後に経由した頂点番号。
なお、頂点iが到達可能な頂点でないときは「-1」とした。swiftらしく、要素の型をInt?として「nil」を使っても良いけど、Optional値を剥くのが面倒なのよね。nil判定でなく、i<0で判定した方が簡単。
- via[i]:Int 頂点iまでの最短距離を実現するとき、最後に経由した頂点番号。
- 最後に、配列viaを使って、下記関数で経由地を配列で出力する。
func route(_ goal:Int)->[Int]{
var g = goal - 1
var ans = [goal] // お尻から詰めていき、最後にreverse()する
var prev = via[g] // 一つ前の経由地
repeat {
if (prev == -1) {return[-1]} // ルートが無いことを[-1]で返す
prev = via[prev]
ans.append(prev + 1) // 配列上の番号に1を足す
} while prev != s // 初めてループのお尻に条件式を使ったかも
ans.reverse()
return ans
}
- コード全体は下記の通り。
let (N,M,s) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1],$0[2]-1)}[0]
var gs = [[(to:Int,weight:UInt64)]](repeating:[],count:N) // 頂点[i]に対して、(繋がっている頂点to、重みweight)のタプルであり、前述のgsと比べて「重み」の情報が追加されている。
for _ in 0..<M {
let (a,b,w) = [readLine()!.split(separator:" ").map{UInt64($0)!}].map{(Int($0[0])-1,Int($0[1])-1,$0[2])}[0]
gs[a].append((b,w))
gs[b].append((a,w))
}
//頂点[i]が到達済みか判定する
var seen = [Bool](repeating:false,count:N)
//頂点[i]に到達したときの直前の頂点番号を格納する【追加】
var via = [Int](repeating:-1,count:N)
//前記seedだけで無く、頂点sから頂点[i]への総距離d[i]を記録する。最短距離になるまで、塗り替えが行われる。
var d = [UInt64](repeating:INF,count:N)
let INF = UInt64.max // 初期値は∞の代わりに、整数の最大値としている。
d[s] = 0 // 頂点sから頂点sへの総距離は当然0となる。
via[s] = s // スタート地点の前の経由地は存在しないが、便宜的に自身の頂点番頭とする【追加】
while (true) {
var dmin_next = INF // 次の頂点を決定するための最短距離の初期値
var v_next:Int? // 次の頂点を格納する変数
for v in 0..<N { //全ての頂点を走査する
if !seen[v] && d[v]<dmin_next { //「頂点vが未到達」かつ「頂点vへの距離計測済みかつ最短」
dmin_next = d[v] // 最短距離を上書き
v_next = v // 最短となる次の頂点を格納 (for文の中で上書きされる可能性有り)
}
}
guard let v = v_next else {break} // 次の頂点が無くなったらループを抜ける
//次の頂点vの更に先の頂点(g.to)までの距離情報を得る
for g in gs[v] {
if d[g.to] > d[v] + g.weight { // d[g.to]の初期値はINF
d[g.to] = d[v] + g.weight
via[g.to] = v // 【追加】
}
}
seen[v] = true // 頂点vは到達済み(観測済み)のフラグを立てる
}
// print(via) [0, 0, 0, 2, 5, 2] // viaの中身を確認
// 結果を表示
for v in 0..<N {
print(v+1,terminator:":") //頂点番号を[i]方式から、問題文の番号に戻す
if d[v]<INF { // 頂点vまで到達できるかどうかを距離がINFか否かで判定
print(d[v],terminator:" ") // 距離(重みの合計)を表示
} else {
print("INF",terminator:" ") // 到達できないとき、INFを表示
}
print("経由情報:",route(v+1)) // 【追加】
}
func route(_ goal:Int)->[Int]{ // 【追加】
var g = goal - 1 // 頂点番号を配列用に1減した。
var ans = [goal] // お尻から詰めていき、最後にreverse()する
var prev = via[g] // 一つ前の経由地
repeat {
if (prev == -1) {return[-1]} // ルートが無いことを[-1]で返す
prev = via[prev]
ans.append(prev + 1) // 配列上の番号に1を足す
} while prev != s
ans.reverse()
return ans
}
- 出力結果は、以下の通り。なお、上記はヒープ導入前のコードだけど、ヒープ導入後の方でも全く同じように経由地情報を追加出来る。
1:0 経由情報: [1, 1]
2:7 経由情報: [1, 2]
3:9 経由情報: [1, 3]
4:20 経由情報: [1, 4]
5:20 経由情報: [1, 3, 5]
6:11 経由情報: [1, 6]
おわりに
- 自分でコードを書いてやっと理解できたわ。
- 文章だけだと、サッパリ頭に入ってこないのは、ある意味病気なのだろうか?ちょっと、自分が心配だわ。