dijkstra.swift

import PlaygroundSupport

class Node: CustomStringConvertible {
    var name = ""
    var edges = [Edge]()

    init(_ name: String) {
        self.name = name
    }

    var description: String {
        return name
    }
}

struct Edge {
    var cost: Int
    var dest: Node

    init(_ cost: Int, _ dest: Node) {
        self.cost = cost
        self.dest = dest
    }
}

func dijkstra(nodes: [Node], start: Node, dest: Node) -> [Node] {
    var queue: [(Node, Int, Node?)] = nodes.map { ($0, $0.name == start.name ? 0 : Int.max, nil) }
    var done = [(Node, Int, Node?)]()
    while !queue.isEmpty {
        let (n, w, p) = queue.min { $0.1 < $1.1 }!
        queue.remove(at: queue.firstIndex(where: { $0.0.name == n.name })!)
        done.append((n, w, p))
        for e in n.edges {
            if let i = queue.firstIndex(where: { $0.0.name == e.dest.name }) {
                if w + e.cost < queue[i].1 {
                    queue[i].1 = w + e.cost
                    queue[i].2 = n
                }
            }
        }
    }
    var na = [Node]()
    var path = done.first { $0.0.name == dest.name }
    while true {
        na.append(path!.0)
        if path!.2 == nil { break }
        path = done.first { $0.0.name == path!.2!.name }
    }
    return na.reversed()
}

let a = Node("A")
let b = Node("B")
let c = Node("C")
let d = Node("D")
let e = Node("E")
let f = Node("F")
let g = Node("G")
let h = Node("H")
let i = Node("I")

a.edges = [Edge(5, b), Edge(3, c), Edge(2, e)]
b.edges = [Edge(2, d)]
c.edges = [Edge(1, b), Edge(1, d)]
d.edges = [Edge(1, a), Edge(2, g), Edge(1, h)]
e.edges = [Edge(1, a), Edge(1, h), Edge(7, i)]
f.edges = [Edge(3, b), Edge(1, g)]
g.edges = [Edge(3, c), Edge(2, i)]
h.edges = [Edge(2, c), Edge(2, f), Edge(2, g)]

let nodes = [a, b, c, d, e, f, g, h, i]

print(dijkstra(nodes: nodes, start: a, dest: i))