四十三庵

蔀の雑記帳

Warshall–Floyd Algorithm

データ構造とアルゴリズム (新・情報 通信システム工学)

  • ダイクストラと発想は同じだが、出発点が存在せず、全ての節点と全ての接点のコストテーブルを更新する
  • コストテーブルのサイズはN*N
  • 計算量はO(N3)
  • 計算量はダイクストラよりN回倍多いが、実装が楽で、接点を結ぶ辺が多い際は有効

実装

import Foundation

let V = ["a", "b", "c", "d"]
let d = [[0, 2, 6, 9],
         [Int.max, 0, 3, Int.max],
         [Int.max, Int.max, 0, 1],
         [2, Int.max, Int.max, 0]
        ]

func Floyd(V: [String], d: [[Int]]) -> [[Int]] {
    var C = d
    for (relayIndex, _) in V.enumerated() {
        for (startIndex, _) in V.enumerated() {
            for (endIndex, _) in V.enumerated() {
                guard C[startIndex][relayIndex] != Int.max && C[relayIndex][endIndex] != Int.max else { continue }
                C[startIndex][endIndex] = min(C[startIndex][endIndex], C[startIndex][relayIndex] + C[relayIndex][endIndex])
            }
        }
    }
    return C
}

print(Floyd(V: V, d: d))