グラフの重み最小経路の経路履歴つき【競技プログラミング】

はじめに

• 最近、グラフ理論の最小経路について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を使って、下記関数で経由地を配列で出力する。

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]

おわりに

• 自分でコードを書いてやっと理解できたわ。
• 文章だけだと、サッパリ頭に入ってこないのは、ある意味病気なのだろうか？ちょっと、自分が心配だわ。