Dijkstra's algorithm finds the lowest-weight paths from one starting vertex to every reachable vertex in a weighted graph. It repeatedly explores the closest known vertex, updates shorter routes, and records the edge that produced each distance. The technique underlies route planning and navigation systems. section 2.4 section 4.4
The algorithm proceeds as follows:
- Add the starting vertex to an ascending priority queue. section 4.4
- Pop the closest vertex and inspect every neighboring edge. section 4.4
- Record a neighbor's distance and incoming edge when no route exists or the new route is shorter. section 4.4
- Repeat until the queue is empty, then return all distances and predecessor edges. section 4.4
A Swift implementation stores optional distances in an array, predecessor edges in a dictionary, and queued vertices in a comparable DijkstraNode. For each edge, it replaces the old distance only when the accumulated weight is smaller. section 4.4
From Los Angeles to Boston
A city graph starting at Los Angeles reports Boston at distance 2605. The recorded path runs through Riverside, Chicago, and Detroit, with edge weights 50, 1704, 238, and 613.
public extension WeightedGraph {
/// Represents a node in the priority queue used
/// for selecting the next
struct DijkstraNode: Comparable, Equatable {
let vertex: Int
let distance: W
public static func < (lhs: DijkstraNode, rhs: DijkstraNode) -> Bool {
return lhs.distance < rhs.distance
}
public static func == (lhs: DijkstraNode, rhs: DijkstraNode)
-> Bool {
return lhs.distance == rhs.distance
}
}
/// Finds the shortest paths from some route vertex to every other
vertex in the graph.
///
/// - parameter graph: The WeightedGraph to look within.
/// - parameter root: The index of the root node to build the shortest
paths from.
/// - parameter startDistance: The distance to get to the root node
(typically 0).
/// - returns: Returns a tuple of two things: the first, an array
containing the distances, the second, a dictionary containing
the edge to reach each vertex. Use the function
pathDictToPath() to convert the dictionary into something
useful for a specific point.
public func dijkstra(root: Int, startDistance: W) -> ([W?],
[Int: WeightedEdge<W>]) {
var distances: [W?] = [W?](repeating: nil, count: vertexCount)
// how far each vertex is from start
distances[root] = startDistance // the start vertex is
startDistance away
var pq: PriorityQueue<DijkstraNode> =
PriorityQueue<DijkstraNode>(ascending: true)
var pathDict: [Int: WeightedEdge<W>] = [Int: WeightedEdge<W>]()
// how we got to each vertex
pq.push(DijkstraNode(vertex: root, distance: startDistance))
while let u = pq.pop()?.vertex { // explore the next closest vertex
guard let distU = distances[u] else { continue } // should
already have seen it
for we in edgesForIndex(u) { // look at every edge/vertex
from the vertex in question
let distV = distances[we.v] // the old distance to
this vertex
if distV == nil || distV! > we.weight + distU { // if
we have no old distance or we found a shorter path
distances[we.v] = we.weight + distU
// update the distance to this vertex
pathDict[we.v] = we // update the edge on the shortest
path to this vertex
pq.push(DijkstraNode(vertex: we.v, distance:
we.weight + distU)) // explore it soon
}
}
}
return (distances, pathDict)
}
/// A convenience version of dijkstra() that allows the supply of
the root
/// vertex instead of the index of the root vertex.
public func dijkstra(root: V, startDistance: W)
-> ([W?], [Int: WeightedEdge<W>]) {
if let u = indexOfVertex(root) {
return dijkstra(root: u, startDistance: startDistance)
}
return ([], [:])
}
/// Helper function to get easier access to Dijkstra results.
public func distanceArrayToVertexDict(distances: [W?]) -> [V : W?] {
var distanceDict: [V: W?] = [V: W?]()
for i in 0..<distances.count {
distanceDict[vertexAtIndex(i)] = distances[i]
}
return distanceDict
}
}
Inspect the Swift extension defining the priority-queue node and shortest-path operation. section 4.4
