A shortest path connects two vertices through a route with the least total cost. In an unweighted graph, breadth-first search finds a route with the fewest edges. section 2.4 section 4.2
Different problems measure and search for the shortest path in different ways:
- Breadth-first search explores a graph by distance layers and can return the shortest route between Boston and Miami in number of edges. section 4.2
- A* uses a heuristic to guide path-finding and appears in route planning, games, and parsing applications. section 2.4
- The traveling salesman problem searches for a shortest cycle that visits every city exactly once and returns to its start. section 8.2
Finding a shortest route with BFS
A graph search keeps a frontier of unexplored vertices, an explored set, and a path dictionary recording how each vertex was reached. Starting at Boston and stopping at Miami produces Boston > Detroit > Washington > Miami: three edges. section 4.2
Exhaustive search for a traveling-salesman route
For five Vermont cities, generate every permutation, append each route's starting city, add its edge distances, and retain the smallest total. The result is Bennington > Brattleboro > White River Junction > Burlington > Rutland > Bennington, totaling 318 miles. section 8.2
extension Graph {
//returns a path to the goal vertex
func bfs(initialVertex: VertexType, goalTestFn:
(VertexType) -> Bool) -> Path? {
guard let startIndex = indexOfVertex(initialVertex)
else { return nil }
// frontier is where we've yet to go
let frontier: Queue<Int> = Queue<Int>()
frontier.push(startIndex)
// explored is where we've been
var explored: Set<Int> = Set<Int>()
explored.insert(startIndex)
// how did we get to each vertex
var pathDict: [Int: EdgeType] = [Int: EdgeType]()
// keep going while there is more to explore
while !frontier.isEmpty {
let currentIndex = frontier.pop()
let currentVertex = vertexAtIndex(currentIndex)
// if we found the goal, we're done
if goalTestFn(currentVertex) {
return pathDictToPath(from: startIndex, to: currentIndex,
pathDict: pathDict)
}
// check where we can go next and haven't explored
for edge in edgesForIndex(currentIndex)
where !explored.contains(edge.v) {
explored.insert(edge.v)
frontier.push(edge.v)
pathDict[edge.v] = edge
}
}
return nil // never found the goal
}
}
Inspect the Swift BFS implementation that reconstructs a shortest path from predecessor edges. section 4.2
