Swift で Dijkstra Algorithm（ダイクストラ法）使ってSSSP：Single Source Shortest Path（単一始点最短経路問題）

Swift で Dijkstra Algorithm を書いたので備忘用にメモ

NOTE

• 実装方法
  • Dijkstra algo の実装方法としては大きく２通り（Naitve array / Primary Queue）あり、それぞれの実装方法によって Time Complexity が変わってくる
• 実装：DP

Naive Array Way

• implementation: naive array
• start from 1-index
• Time Complexity: O(V^2) (V: number of vertexes)

struct Edge {
    let to: Int
    let weight:Int
}

// List does not use 0-index but starts from 1-indexrunning.
// n: number of nodes
// k: start node
func dijkstra(_ adjList: [[Edge]], _ n: Int, _ k: Int) -> ([Int], [Bool]){
    var visited = [Bool](repeating: false, count: n+1)
    var dist = [Int](repeating: Int.max, count: n+1)
    visited[0] = true // no need 0-index
    dist[0] = -1      // no need 0-index
    
    // init
    dist[k] = 0
    
    // loop for all nodes
    for _ in 1...n { // O(V)
        // find vertex:
        //   which is not visited yet.
        //   whose dist is smallest
        let minVertex: Int = { // O(V)
            var minDist = Int.max // placeholder
            var minVertex = -1    // placeholder
            for vertex in 1...n { // nodes are at 1 to n
                if visited[vertex] { continue }
                if minDist > dist[vertex] {
                    minDist = dist[vertex]
                    minVertex = vertex
                }
            }
            return minVertex
        }()
        
        // quick return
        if minVertex == -1 { break }
        
        // run the relaxation
        let from = minVertex
        let adj = adjList[from]
        for edge in adj {
            let to = edge.to
            let w = edge.weight
            if dist[to] > dist[from] + w {
                dist[to] = dist[from] + w
            }
        }

        // visit
        visited[minVertex] = true
    }
    return (dist, visited)
}

PQ Way

• implementation: Primary Queue
• start from 1-index
• Comparison to naive array:
  • Improving find minVertex process with Heap. Time Complexity is changed O(V) to O(logV).
  • Deteriorating to update store as PQ from O(1) to O(log V)

Way1

けんちょん本の方法

// Before running, need a ready for IndexPriorityQueue, CompVertex.

func dijkstra(_ adjList: [[Edge]], _ n: Int, _ k: Int) -> ([Int], [Bool]){
    var visited = [Bool](repeating: false, count: n+1)
    var dist = [Int](repeating: Int.max, count: n+1)
    visited[0] = true // no need 0-index
    dist[0] = -1      // no need 0-index
    
    // init
    dist[k] = 0
    visited[k] = true
    var pq = PQ<CompVertex>(<) // min-heap
    pq.enqueue(CompVertex(v: k, d: dist[k]))
    
    // loop for all nodes
    while let vertex = pq.dequeue() {
        let v = vertex.v; let d = vertex.d; 
        if d > dist[v] { continue } // ignore because thsi is old info.
        for edge in adjList[v] { // next edges
            if dist[edge.to] > edge.weight + dist[v] {
                dist[edge.to] = edge.weight + dist[v]
                pq.enqueue(CompVertex(v: edge.to, d: dist[edge.to]))
            }
        }
        visited[v] = true
    }
    
    return (dist, visited)
}

Way2

func dijkstra(_ adjList: [[Edge]], _ n: Int, _ k: Int) -> ([Int], [Bool]){
    var visited = [Bool](repeating: false, count: n+1)
    var dist = [Int](repeating: Int.max, count: n+1)
    visited[0] = true // no need 0-index
    dist[0] = -1      // no need 0-index
    
    // init
    dist[k] = 0
    visited[k] = true
    var pq = PQ<CompEdge>(<)
    for edge in adjList[k] {
        pq.enqueue(CompEdge(to: edge.to, d: edge.weight))
    }
    
    // loop for all nodes
    while let edge = pq.dequeue() {
        if dist[edge.to] > edge.d {
            dist[edge.to] = edge.d
            for nextEdge in adjList[edge.to] {
                pq.enqueue(CompEdge(to: nextEdge.to, d: dist[edge.to] + nextEdge.weight))
            }
            visited[edge.to] = true
        }
    }
    
    return (dist, visited)
}

---

MEMO

Relaxation

if dist[to] > dist[from] + weight {
    dist[to] = dist[from] + weight
}

// or

dist[to] = min(dist[to], dist[from] + weight)