Implementation of Bellman–Ford algorithm in Swift

BellmanFord.swift

/////////////////////////////////////////////////////// THEORY ///////////////////////////////////////////////////////
//
// Source: https://en.wikipedia.org/wiki/Bellman–Ford_algorithm
//
//
// function BellmanFord(list vertices, list edges, vertex source)::distance[],predecessor[]
//   // This implementation takes in a graph, represented as
//   // lists of vertices and edges, and fills two arrays
//   // (distance and predecessor) with shortest-path
//   // (less cost/distance/metric) information
//
//   // Step 1: initialize graph
//   for each vertex v in vertices:
//     if v is source then distance[v] := 0
//     else distance[v] := inf
//     predecessor[v] := null
//
//   // Step 2: relax edges repeatedly
//   for i from 1 to size(vertices)-1:
//     for each edge (u, v) with weight w in edges:
//       if distance[u] + w < distance[v]:
//         distance[v] := distance[u] + w
//         predecessor[v] := u
//
//   // Step 3: check for negative-weight cycles
//   for each edge (u, v) with weight w in edges:
//     if distance[u] + w < distance[v]:
//       error "Graph contains a negative-weight cycle"
//
//   return distance[], predecessor[]

/////////////////////////////////////////////////////// ALGORITHM ///////////////////////////////////////////////////////

typealias Weight = Double
typealias Vertex = Int
typealias Edge = (Vertex, Vertex, Weight)
typealias Path = Array<Vertex>

enum BellmanFordResult {
    case ShortestPath(Path)
    case Error(String)
}

func bellmanFord(source:Vertex, sinc: Vertex, vertices: [Vertex], edges: [Edge]) -> BellmanFordResult {
    let infinity = Weight(LONG_MAX)
    var distance = [Vertex: Weight]()
    var predecesor = [Vertex: Vertex]()
    
    // Step 1: initialize graph
    for vertex in vertices {
        if vertex == source {
            distance[vertex] = 0
        } else {
            distance[vertex] = infinity
        }
    }
    
    // Step 2: relax edges repeatedly
    for i in 1..<vertices.count {
        for (u, v, w) in edges {
            if  let dist_u = distance[u],
                let dist_v = distance[v] {
                    if dist_u + w < dist_v {
                        distance[v] = dist_u + w
                        predecesor[v] = u
                    }
            } else {
                return .Error("Vertix from edge (\(u), \(v)) not in list of of vertices \(vertices)")
            }
        }
    }
    
    // Step 3: check for negative-weight cycles
    for (u, v, w) in edges {
        if  let dist_u = distance[u],
            let dist_v = distance[v] {
                if dist_u + w < dist_v {
                    return .Error("Graph contains a negative-weight cycle")
                }
        } else {
            return .Error("Vertix from edge (\(u), \(v)) not in list of of vertices \(vertices)")
        }
    }
    
    // Step 4: extract shortest path from list of predecesors
    var path = Path()
    var v = sinc
    while true {
        path.append(v)
        if v == source {
            break
        } else {
            if let pred = predecesor[v] {
                v = pred
            } else {
                return .Error("Error forming shortest path from list of predecesors \(predecesor)")
            }
        }
    }
    
    return .ShortestPath(path.reverse())
}

/////////////////////////////////////////////////////// TESTING ///////////////////////////////////////////////////////

let vertices: [Vertex] = [1, 2, 3, 4, 5, 6, 7]
let edges: [Edge] = [(1, 2, 5), (1, 3, 3), (1, 4, 5), (1, 5, 6), (1, 6, 8), (2, 4, 1), (2, 5, 4), (3, 5, 2), (4, 5, 3), (4, 6, 5), (5, 6, 5), (5, 7, 6), (6, 7, 5)]

switch bellmanFord(1, 7, vertices, edges) {
case .ShortestPath(let path):   println("Shortest path: \(path)")
case .Error(let reason):        println("Error: \(reason)")
}