Swift Algorithms & Data Structures

Dijkstra Algorithm (version 2)

This source code is supporting material for the essay on binary heaps.

//an optimized version of Dijkstra's shortest path algorithm
func processDijkstraWithHeap(source: Vertex, destination: Vertex) -> Path! {
    var frontier: PathHeap = PathHeap()
    var finalPaths: PathHeap = PathHeap()

    //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.enQueue(newPath)
    }

    //construct the best path
    var bestPath: Path = Path()

    while(frontier.count != 0) {
        //use the greedy approach to obtain the best path
        bestPath = Path()
        bestPath = frontier.peek()

        //enumerate the bestPath edges
        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.enQueue(newPath)#sthash.TL5TqZnP.dpuf
        }

        //preserve the bestPaths that match destination
        if (bestPath.destination.key == destination.key) {
            finalPaths.enQueue(bestPath)
        }

        //remove the bestPath from the frontier
        frontier.deQueue()

    } //end while

    //obtain the shortest path from the heap
    var shortestPath: Path! = Path()
    shortestPath = finalPaths.peek()

    return shortestPath

}