グラフの重み最小経路について【競技プログラミング】

始めに

• ABC362のd問題で、とうとう重み有りのグラフ問題とご対面してしまったので、勉強してみた。ちなみに、コードはswiftで書いてます。
• さすがにこれは、前知識無しで解けるものではなかったよ。事前に、頂点aから頂点bまでの経路の有無についての問題は解いてたんだけどなあ。
• ちなみに、グラフとは、これ。丸い部分を「頂点」（Vertex:Vと表現される）と呼び、線の部分を「辺」（Edge:Eと表現される。）と呼ぶ。例えば「頂点」を場所として、「辺」を道路として、各道路に距離（グラフ理論では「重み」と呼ぶ）を割り当てて、ある場所からある場所までの最短距離を求めることが出来る。詳しくはwikiを見て。
  

復習（頂点aから頂点bまで繋がっているかどうか）

• まずは、グラフ問題の初歩として、経路があるかどうかの問題を解いてみる。
• サンプルとして、ABC284のc問題をとりあげる。
  
• 上記のグラフは、下記入力のように表現される

5 3 // 頂点の数5、辺の数3
1 2 // 辺1：頂点1と頂点2を結ぶ線
1 3 // 辺2：頂点1と頂点3を結ぶ線
4 5 // 辺3：頂点4と頂点5を結ぶ線

• そして、上記グラフを取り込むプログラムは次のとおり

//グラフ取込み（無指向辺）頂点番号1減済み
let (N,M) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]

var gs = [[Int]](repeating:[],count:N) // gはグラフのg、sは配列だから複数形の意味でs
for _ in 0..<M {
    let (a,b) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0]-1,$0[1]-1)}[0]
    gs[a] += [b]
    gs[b] += [a] // 無指向辺のため、逆向き(b⇒a)のデータも追加
}

print(gs) // [[1, 2], [0], [0], [4], [3]]

• 上記についての解説

  • グラフ問題では、頂点の番号が1から始まるけど、プログラムで扱うときは0から始まる方が良いので、頂点番号は取込時点で「-1」している。問題文の番号と紛らわしいので、以下では、0スタートの頂点番号は[0]のように表現する。
  • gsの最初の要素（インデックス:0）は、頂点[0]と辺で繋がっている頂点[1]、頂点[2]を指す。gs[1]、gs[2]の要素[0]は、それぞれ、頂点[1]、頂点[2]と辺で繋がっているのが頂点[0]であることを意味する。

• c問題を解く前に、スタート地点s(1〜5のどれか)から、各頂点にたどり着けるかどうかを判定するプログラムを作成する。

• そのため、まずは、スタート地点を取り込むため、上記入力の1行目を5 3 1(スタート地点が1の場合)のように変える。

• この場合のコードは

//グラフ取込み（無指向辺）頂点番号1減済み
let (N,M,s) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1],$0[2]-1)}[0] // sを追加

var gs = [[Int]](repeating:[],count:N)
for _ in 0..<M {
    let (a,b) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0]-1,$0[1]-1)}[0]
    gs[a] += [b]
    gs[b] += [a]
}

print(gs) // [[1, 2], [0], [0], [4], [3]]

// 上記グラフで、頂点sからの到達可能頂点はtrueとなる（自頂点同士[0->0等]も含む）
var seen = [Bool](repeating:false,count:N)

func dfs(_ n:Int){ //頂点nから到達可能な頂点を示すseenの配列をtrueにする
    if seen[n] {return}
    seen[n] = true
    for nn in gs[n] {dfs(nn)} //頂点nから到達可能な頂点で再帰的にtrueを埋めていく
}

print(s) // 1：頂点[0]のこと
dfs(s)

print(seen) // [true, true, true, false, false] 頂点[0][1][2]が到達可能

• 上記についての解説
  • 配列seenは、最初falseで埋めて、頂点sから到達可能なときにtrueに変わる。
  • 関数dfs(深さ優先探索:Depth First Search)は再帰関数となっている。まず最初に自頂点番号を引数として受け取り、seen配列の自頂点番号をtrueに変えた後、gs配列により、自頂点から到達可能な頂点番号で、再帰的にdfs関数が実行されるため、自頂点から到達可能な頂点全てでseen配列がtrueとなる。
• ABC284のc問題に戻ると、この問題は「連結成分の個数」が回答となっている。連結成分とは、つまり、繋がっている頂点同士のことであり、この1まとまりを1個と数えれば、上記のグラフは、｛1,2,3｝｛4,5｝の2個の連結成分となる。
• この連結成分の個数を求めるコードは

//グラフセット（無指向辺）頂点番号1減済み
let (N,M) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]

var gs = [[Int]](repeating:[],count:N)
for _ in 0..<M {
    let (a,b) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0]-1,$0[1]-1)}[0]
    gs[a] += [b]
    gs[b] += [a]
}

var seen = [Bool](repeating:false,count:N)

func dfs(_ n:Int){ //頂点nから到達可能な頂点を示すseenの配列をtrueにする
    if seen[n] {return}
    seen[n] = true
    for nn in gs[n] {dfs(nn)} 
}

// 回答となる変数
var ans = 0

for s in 0..<N {
    if seen[s] {continue} // 既に到達可能判定されていれば、スキップ
    ans += 1 // 未到達頂点でdfsを実行する度に1加算
    dfs(s)
}

// print(seen) // [true, true, true, true, true]
print(ans) // 2

本題（頂点aから頂点bへの最短経路）

• 重みがあるグラフでの最短経路は、一般的にはダイクストラ法を使う。
• 下記は頂点1から各頂点への最短経路を求めるアルゴリズムをgif化したもの。各頂点への距離を最初は∞にしておいて、最短距離が確定したら、上書きしていく。例えば、頂点1からは、頂点2,3,6への経路があるが、最短距離は頂点2への距離7となっている。よって、頂点1から頂点2への最短経路として、頂点3,6を経由する経路が選ばれることはあり得ないため、頂点2への最短経路は確定した。つぎは、頂点1と頂点2への最短経路を所与のものとして、次の最短経路を探すと、頂点3への距離9が最短であることが判明する（頂点6への「14」、頂点4への「22」、頂点3への頂点2経由「17」と比べて短い）。この作業を続けて、全ての頂点への最短経路が決まるまで続ける
  
• コードで書くと

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))
}

//前述のseenと同様、頂点[i]が到達済みか判定する
var seen = [Bool](repeating:false,count:N)

//前記seedだけで無く、頂点sから頂点[i]への総距離d[i]を記録する。最短距離になるまで、塗り替えが行われる。
var d = [UInt64](repeating:INF,count:N)
let INF = UInt64.max // 初期値は∞の代わりに、整数の最大値としている。

d[s] = 0 // 頂点sから頂点sへの総距離は当然0となる。

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
        }
    }
    
    seen[v] = true // 頂点vは到達済み（観測済み）のフラグを立てる
}

// 結果を表示
for v in 0..<N {
        print(v+1,terminator:":") //頂点番号を[i]方式から、問題文の番号に戻す
    if d[v]<INF { // 頂点vまで到達できるかどうかを距離がINFか否かで判定
        print(d[v]) // 距離(重みの合計)を表示
    } else {
        print("INF") // 到達できないとき、INFを表示
    }
}

• 上記のコードの解説は特にしないけど、コード中のコメントを見てくれれば分かると思う。
• 入力(上記のgifを例とした)

6 9 1 // 頂点の数6、辺の数9，スタート頂点1
1 2 7 // 辺1：頂点1と頂点2を結ぶ辺の重み7
1 3 9 // 辺2：頂点1と頂点3を結ぶ辺の重み9
1 6 14
2 3 10
2 4 15
3 4 11
6 3 2
6 5 9
4 5 6

• 出力(上記のgifと一致している)

1:0 //頂点1から頂点1への距離は当然0
2:7 //頂点1から頂点2への最短距離は7
3:9 //頂点1から頂点3への最短距離は9
4:20
5:20
6:11

最初の目的(ABC362のd問題を解く)

• a,b,c問題まで終わった時点で1時間くらい残ってたから、上記を先週までに勉強しておけば、余裕で初の4完できたのに(号泣)
• それはさておき、d問題については、下記コードで解答できる。通常の重み最小経路問題とは、「頂点にも重みがある」という点だけ異なるけど、基本的には頂点の重みを辺の重みに上乗せするだけで、通常の問題に変換できる。
• 入力例

5 8 // 頂点5個、辺8本
928448202 994752369 906965437 942744902 907560126 //各頂点の重み
2 5 975090662 // 辺1：頂点2から頂点5への重み975090662(無向グラフだから、5⇒2もあり)
1 2 908843627
1 5 969061140
3 4 964249326
2 3 957690728
2 4 942986477
4 5 948404113
1 3 988716403

• ちょこっと変えるだけで完成！

let (N,M) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]

let As = readLine()!.split(separator:" ").map{UInt64($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 + As[b])) //辺の「先」の頂点の重みを加算
    gs[b].append((a,w + As[a])) //辺の「先」の頂点の重みを加算
}

//前述のseenと同様、頂点[i]が到達済みか判定する
var seen = [Bool](repeating:false,count:N)

//前記seedだけで無く、頂点sから頂点[i]への総距離d[i]を記録する。最短距離になるまで、塗り替えが行われる。
var d = [UInt64](repeating:INF,count:N)
let INF = UInt64.max // 初期値は∞の代わりに、整数の最大値としている。

d[0] = 0 // 頂点0から頂点0への総距離は当然0となる。

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
        }
    }
    
    seen[v] = true // 頂点vは到達済み（観測済み）のフラグを立てる
}

// 結果を表示
for v in 1..<N { //スタートとなる頂点は[0]
    print(d[v] + As[0],terminator:" ") // 最後に頂点[0]の重みを加算
}

• 出力 2832044198 2824130042 4696218483 2805069468 よっしゃ正解！...と思うじゃん？
• でも、AtCoderで提出すると、半分近くのTLE続出。
• 知ってた。なんとなく使ってるwhile(true)とか、for v in 0..<N { //全ての頂点を走査するみたいな線形走査とか、こんなヌルいコードじゃ厳しいだろうなって...

計算量の削減方法(ヒープの導入)

• じつは、本題（頂点aから頂点bへの最短経路）で書いたコードは、計算量$O(N^2)$となるコードで、条件が 「$2≤N≤2×10^5$」の場合、$10^8$を余裕で超えちゃうのよね。
• 高速化のため「ヒープ」を導入するといいらしい。ヒープを使うと、なんと、計算量が$O(E･logN)$に激減！安い！安いですよ奥さん！....え？その前に、ヒープって何？
• と言うわけで、ヒープに寄り道します。

【寄り道】ヒープについて【迷子】

• とりあえず、知らない言葉が出てきたときは迷わずwikiをみる。ざっと見た感じ、配列やキューやスタックみたいな、「データ構造」の一種みたい。例えば、配列は、指定したインデックスの要素の読み取りや最後尾への要素の追加は高速(O(1))だけど、最後尾以外のインデックスへの要素追加や削除は激重(先頭要素の削除はO(n))だし、sortはO(N･logN)となる。
• wikiを見ると、ヒープは最大値や最小値を取得するのに適したデータ構造らしいけど、具体的には、以下のツリー構造（例：二分ヒープ）をしている。各頂点の番号は、親の頂点番号からみて、左下が2i、右下が2i+1の関係にすると、綺麗に頂点番号が重ならず埋まっていく。
  
• ちなみに「heap」とは「積み重なったもの」という意味で、pile(トランプのカードを重ねた「山」に対して使用)より規模が大きいものに対して使う。若干マイナス用を含み、ゴミが「山」になってる、とか、古新聞紙の束、とかに使う。
• 以下は、二分ヒープについての説明となる。二分ヒープは「最大ヒープ」と「最小ヒープ」の2種類あるが、下図は「最大ヒープ」であり、以下の制約がある。なお、丸内の数値は、頂点に格納されている要素の値。なお、値は整数である必要は無く、値に「順番」が存在すれば良い。
  1. 各々のノードはそのノードの子よりも大きいか等しくなるように配置される
  2. 木は完全にバランスの取れた二分木（すべての葉は同じ高さにある）になるか、木のもっとも高い方がすべて埋まっていないならば、ノードは左から右へ順に埋まっていく
     
• 先にヒープの特徴を言ってしまうと、「最大ヒープ」の場合は、最大値の取得は当然O(1)となる。値の削除や追加はについて、一覧化すると、以下の通り。要素の削除は若干遅いものの、配列よりは断然早く、追加については、圧倒的に速い。よって、値の削除追加を頻繁に行う作業の場合は、配列よりヒープを使う方が有利となる。
  
• ちなみに、c++やPythonでは、ヒープが最初から実装されているものの、swiftにはないので、自作する必要がある。面倒くさいなぁ、と思ったら、こんなライブラリがあった！Heapもあるじゃん！...あれ？でも、paiza.ioやAtCoderでは使えないや...残念。もちろん、playgroundsでは使えたけどね。
  
  
• え〜、実装面倒だなぁ。でも、頑張ってみる。つか、AtCoderでswiftでAC取った人のコードを頂いてしまえば良いのでは？いただき男子したら、懲役9年とかかなぁ。インスパイアとか適当言っておけば、許されるかな？と思ったけど、心配無用でした。swiftでd問題ACの人はゼロでした。swift6.0で"swift-collections"をふくめてくれないかなぁ。ここまで出来てんだし。
• とりあえず、寄り道失敗！迷子になったよ！
• 誰もswiftでACしてないのは、swiftでのヒープの実装が面倒だからかな。
• 続きは、また今度ね　↓続きはこちら！↓

最後に

• c++やpythonでは、ヒープが実装されているのに、swiftにないとか、悲しすぎた。
• swift6.0でswift-collectionsが正式に導入されるのを待つか、自分で実装するか、迷うところです。
• まぁ、実装と言っても、ダイクストラ法で利用する部分だけ構築すれば良いと思えば、大したことないのかも？
• 頑張ってみます。