dijkstra.swift

//
//  main.swift
//  dijkstra
//
//  Created by Owen Morgan on 28/09/2018.
//  Copyright © 2018 Owen Morgan. All rights reserved.
//

import Foundation

class Node <T : Hashable> {
    
    let value : T
    var connections : [Edge<T>]
    
    init(withValue value : T, connectedTo connections : [Edge<T>]) {
        self.value = value
        self.connections = connections
    }
}

struct Edge <T : Hashable> {
    let weight : UInt
    let neighbour : Node<T>
}

func findMinimumDistanceNode<T>(_ distances : [T: UInt], fromNodes nodeSet : [T: Node<T>]) -> Node<T>? {
    
    var minimumNode : Node<T>? = nil
    var maxDistance = UInt.max
    
    for (nodeKey, node) in nodeSet {
        if let distance = distances[nodeKey] {
            if distance < maxDistance {
                maxDistance = distance
                minimumNode = node
            }
        }
    }
    return minimumNode
}

func dijkstraMinimumPath<T>(_ nodes : [Node<T>], startingFrom start : T, goingTo end : T) -> (UInt, [T: UInt]) {
    
    var nodeSet : [T: Node<T>] = [:]
    var distances : [T: UInt] = [:]
    
    for node in nodes {
        nodeSet[node.value] = node
        distances[node.value] = UInt.max
    }
    
    distances[start] = 0
    
    guard let _ = nodeSet[start] else {
        return (UInt.max, [:])
    }
    
    guard let _ = nodeSet[end] else {
        return (UInt.max, [:])
    }
    
    while nodeSet.isEmpty == false {
        
        // force unwrap - in this algorithm we guarantee that distances
        // contains the superset of nodes held in nodeSet
        let node = findMinimumDistanceNode(distances, fromNodes: nodeSet)!
        
        nodeSet.removeValue(forKey: node.value)
        
        for nodeEdges in node.connections {
            let alternativeDistance = distances[node.value]! + nodeEdges.weight
            let neighbouringDistance = distances[nodeEdges.neighbour.value]!
            
            if alternativeDistance < neighbouringDistance {
                distances[nodeEdges.neighbour.value] = alternativeDistance
            }
        }
    }
    
    return (distances[end]!, distances)
}

var nodes = [
    Node<UInt>(withValue: 0, connectedTo: []),
    Node<UInt>(withValue: 1, connectedTo: []),
    Node<UInt>(withValue: 2, connectedTo: []),
    Node<UInt>(withValue: 3, connectedTo: []),
    Node<UInt>(withValue: 4, connectedTo: []),
    Node<UInt>(withValue: 5, connectedTo: []),
]

// Wire up the edges
nodes[0].connections.append(Edge<UInt>(weight: 7, neighbour: nodes[1]))
nodes[0].connections.append(Edge<UInt>(weight: 9, neighbour: nodes[2]))
nodes[0].connections.append(Edge<UInt>(weight: 14, neighbour: nodes[5]))

nodes[1].connections.append(Edge<UInt>(weight: 7, neighbour: nodes[0]))
nodes[1].connections.append(Edge<UInt>(weight: 10, neighbour: nodes[2]))
nodes[1].connections.append(Edge<UInt>(weight: 15, neighbour: nodes[3]))

nodes[2].connections.append(Edge<UInt>(weight: 9, neighbour: nodes[0]))
nodes[2].connections.append(Edge<UInt>(weight: 10, neighbour: nodes[1]))
nodes[2].connections.append(Edge<UInt>(weight: 11, neighbour: nodes[3]))
nodes[2].connections.append(Edge<UInt>(weight: 2, neighbour: nodes[5]))

nodes[3].connections.append(Edge<UInt>(weight: 15, neighbour: nodes[1]))
nodes[3].connections.append(Edge<UInt>(weight: 11, neighbour: nodes[2]))
nodes[3].connections.append(Edge<UInt>(weight: 6, neighbour: nodes[4]))

nodes[4].connections.append(Edge<UInt>(weight: 6, neighbour: nodes[3]))
nodes[4].connections.append(Edge<UInt>(weight: 9, neighbour: nodes[5]))

nodes[5].connections.append(Edge<UInt>(weight: 14, neighbour: nodes[0]))
nodes[5].connections.append(Edge<UInt>(weight: 2, neighbour: nodes[2]))
nodes[5].connections.append(Edge<UInt>(weight: 9, neighbour: nodes[4]))

print(dijkstraMinimumPath(nodes, startingFrom: 0, goingTo: 4))