Swift Algorithms & Data Structures

Dijkstra Algorithm (version 1)

This source code is supporting material for the essay on shortest paths.

//process Dijkstra's shortest path algorthim
func processDijkstra(source: Vertex, destination: Vertex) -> Path? {

    var frontier: Array = Array()
    var finalPaths: Array = 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)
    }

    //construct 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]

            if (bestPath.total == nil) || (itemPath.total < bestPath.total) {
                bestPath = itemPath
                pathIndex = x
            }
        }

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

        //preserve the bestPath
        finalPaths.append(bestPath)

        //remove the bestPath from the frontier
        frontier.removeAtIndex(pathIndex)

    } //end while

    //establish the shortest path as an optional
    var shortestPath: Path! = Path()

    for itemPath in finalPaths {
        if (itemPath.destination.key == destination.key) {
            if (shortestPath.total == nil) || (itemPath.total < shortestPath.total) {
                shortestPath = itemPath
            }
        }
    }

    return shortestPath
}