四十三庵

蔀の雑記帳

Dijkstra Algorithm

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

  • 有向グラフの最短経路を見つけるためのアルゴリズム
  • 計算コストはO(N2)
  • 経路コストの計算にヒープを使うと、約O(2NlogN)までパフォーマンスが改善する
    • 節点と辺の数が同程度の時に限るらしい
    • 辺が多くなる(例えば全ての節点がつながれた完全グラフの時)はパフォーマンスがむしろ落ちる
  • 実装的には経路コストが一番小さい節点を見つけて、そのインデックスを正確にとるのに手間取った (途中で最小コストの要素を配列から削除していく)

実装

import Foundation

let V = ["s", "a", "b", "c"]
let d = [[0, 2, 6, Int.max],                        // s -> x
         [Int.max, 0, 3, Int.max],                  // a -> x
         [Int.max, Int.max, 0, 2],                  // b -> x
         [Int.max, Int.max, Int.max, 0]             // c -> x
        ]

func Dijkstra(V: [String], d: [[Int]]) -> [Int] {
    var C = [Int]()
    
    for v in 0 ..< V.count {
        C.append(d[0][v])
    }

    var U = V
    var tempC = C
    U.removeFirst() // sを削除
    tempC.removeFirst()// sのコストを削除

    while !U.isEmpty {
        let minIndex = minimumCostIndex(where: tempC)!
        let w = index(in: V, by: U[minIndex])!
        U.remove(at: minIndex)
        tempC.remove(at: minIndex)
        for value in U {
            let u = V.firstIndex(of: value)!
            guard d[w][u] != Int.max else { break }
            C[u] = min(C[u], C[w] + d[w][u])
        }
    }
    return C
}

private func minimumCostElement(where costs: [Int]) -> Int? {
    return costs.min()
}

private func minimumCostIndex(where costs: [Int]) -> Int? {
    guard let element = minimumCostElement(where: costs) else { return nil }
    return costs.firstIndex(of: element)
}

private func index(in array: [String], by element: String) -> Int? {
    return array.firstIndex(of: element)
}

print(Dijkstra(V: V, d: d))