Closest-first

Visits vertices in order of their distance from a start vertex, nearest first.

Time complexity O(E log V), gograph function traverse.NewClosestFirstIterator.

How it works

Closest-first keeps a priority queue of vertices by their distance from the start, the sum of the edge weights along the best path found so far. It takes the nearest vertex it hasn't visited, then adds each unvisited neighbor with the distance through that vertex. The vertices come out in order of distance, nearest first.

It is Dijkstra's algorithm as an iterator. Each call to Next returns the next vertex whose distance is final, so a search can stop at the vertex it needs without settling the rest of the graph. It costs O(E log V). Edge weights must not be negative, or a vertex can come out before a cheaper path to it is found.

The iterator returns the vertices, not their distances. Use it when the order matters, such as the three stores nearest to a home, and path.Dijkstra when you need the numbers.

School run

Six places on the morning drive to school. Most streets go both ways, and each edge is the travel time in minutes.

A directed, weighted graph with 6 vertices and 13 edges.

List the places you can drive to from home, nearest by travel time first.

From Home, closest-first visits 6 vertices, nearest first: Home, Bridge, Bakery, Park, Library and School.

Step by step

Every distance starts at ∞, except Home, which is 0. Put Home in the queue at 0.
Take Home from the front of the queue and visit it. Its distance is 0.
Home to Bakery: 0 + 4 = 4. Put Bakery in the queue at 4.
Home to Bridge: 0 + 3 = 3. Put Bridge in the queue at 3.
Take Bridge from the front of the queue and visit it. Its distance is 3.
Bridge to Park: 3 + 2 = 5. Put Park in the queue at 5.

10 more steps lead to the last one:

Done. Closest-first visited 6 vertices from Home, nearest first.

Use it in Go

it, err := traverse.NewClosestFirstIterator(g, "Home")
if err != nil {
	return err
}
for it.HasNext() {
	fmt.Println(it.Next().Label())
}

Example graphs

School run, 6 vertices and 13 edges
Delivery area, 8 vertices and 12 edges
Downtown grid, 20 vertices and 60 edges
One-way city, 45 vertices and 88 edges
Metro region, 100 vertices and 346 edges