Swift - Shortest Path Algorithm (Compiled from: http://waynewbishop.com/swift/graphs/dijkstra/)

Swift - Dijkstra.swift

import UIKit

public class Vertex {
    var key: String?
    var neighbors: Array<Edge>
    init() {
        self.neighbors = Array<Edge>()
    }
}

public class Edge {
    var neighbor: Vertex
    var weight: Int
    init() {
        weight = 0
        self.neighbor = Vertex()
    }
}

class Path {
    var total: Int!
    var destination: Vertex
    var previous: Path!
    
    //object initialization
    init(){ destination = Vertex() }
}

public class SwiftGraph {
    private var canvas: Array<Vertex>
    public var isDirected: Bool
    init() {
        canvas = Array<Vertex>()
        isDirected = true
    }
    //create a new vertex 
    func addVertex(key: String) -> Vertex {
        //set the key 
        var childVertex: Vertex = Vertex()
        childVertex.key = key
        //add the vertex to the graph canvas 
        canvas.append(childVertex)
        return childVertex
    }
    func addEdge(source: Vertex, neighbor: Vertex, weight: Int) {
        //create a new edge 
        var newEdge = Edge()
        //establish the default properties 
        newEdge.neighbor = neighbor
        newEdge.weight = weight
        source.neighbors.append(newEdge)
        //check for undirected graph 
        if (isDirected == false) {
            //create a new reversed edge 
            var reverseEdge = Edge()
            //establish the reversed properties 
            reverseEdge.neighbor = source
            reverseEdge.weight = weight
            neighbor.neighbors.append(reverseEdge)
        }
    }
    func processDijkstra(source: Vertex, destination: Vertex) -> Path? {
        var frontier: Array = []
        var finalPaths: Array = []
        //use source edges to create the frontier
        for e in source.neighbors {
            var newPath: Path = Path()
            newPath.destination = e.neighbor
            newPath.previous = nil
            newPath.total = e.weight
            //add the new path to the frontier
            frontier.append(newPath)
        }
        
        //obtain the best path
        var bestPath: Path = Path()
        while(frontier.count != 0) {
            //support path changes using the greedy approach
            bestPath = Path()
            var x: Int = 0
            var pathIndex: Int = 0
            for (x = 0; x < frontier.count; x++) {
                var itemPath: Path = frontier[x] as Path
                if (bestPath.total == nil) || (itemPath.total < bestPath.total) {
                    bestPath = itemPath
                    pathIndex = x
                }
            }
            
            for e in bestPath.destination.neighbors {
                var newPath: Path = Path()
                newPath.destination = e.neighbor
                newPath.previous = bestPath
                newPath.total = bestPath.total + e.weight
                //add the new path to the frontier
                frontier.append(newPath)
            }
            //preserve the bestPath
            finalPaths.append(bestPath)
            //remove the bestPath from the frontier
            frontier.removeAtIndex(pathIndex)
        }
        printSeperator("FINALPATHS")
        printPaths(finalPaths as [Path], source: source)
        printSeperator("BESTPATH BEFORE")
        printPath(bestPath, source: source)
        for p in finalPaths {
            var path = p as Path
            if (path.total < bestPath.total) && (path.destination.key == destination.key){
                bestPath = path
            }
        }
        printSeperator("BESTPATH AFTER")
        printPath(bestPath, source: source)
        return bestPath
    }
    
    func printPath(path: Path, source: Vertex) {
        println("BP: weight- \(path.total) \(path.destination.key!) ")
        if path.previous != nil {
            printPath(path.previous!, source: source)
        } else {
            println("Source : \(source.key!)")
        }
    }
    
    func printPaths(paths: [Path], source: Vertex) {
        for path in paths {
            printPath(path, source: source)
        }
    }
    
    func printLine() {
        println("*******************************")
    }
    
    func printSeperator(content: String) {
        printLine()
        println(content)
        printLine()
    }
}



var graph = SwiftGraph()
var a = graph.addVertex("a")
var a1 = graph.addVertex("a1")
var b = graph.addVertex("b")
var c = graph.addVertex("c")
var d = graph.addVertex("d")
graph.addEdge(a, neighbor: d, weight: 1)
graph.addEdge(a, neighbor: d, weight: 30)
graph.addEdge(a, neighbor: a1, weight: 30)
graph.addEdge(a1, neighbor: b, weight: 10)
graph.addEdge(a, neighbor: b, weight: 5)
graph.addEdge(b, neighbor: c, weight: 21)
graph.addEdge(c, neighbor: d, weight: 5)

var path = graph.processDijkstra(a, destination: d)