Closest-first
Visits vertices in order of their distance from a start vertex, nearest first.
Time complexity O(E log V), gograph function traverse.ClosestFirst.
traverse.NewClosestFirstIterator gives the same order one Next at a time, without the distances.
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 puts each unvisited neighbor in the queue at the distance through that vertex, or moves it up the queue if that distance is shorter than the one it has. The vertices come out in order of distance, nearest first.
It is Dijkstra's algorithm as an iterator. traverse.ClosestFirst returns an iter.Seq2 of each vertex with its distance, and each one it yields is final, so a range loop can break 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.
Use it when the order matters, such as the three stores nearest to a home, and path.Dijkstra when you need the distance to every vertex at once.
One-way city
Forty-five intersections, I1 to I45, where I stands for intersection, numbered row by row from the top left with nine to a row. Most streets are one way, and the outer streets form a clockwise loop. Only the middle row (I19 to I27) and the middle column (I5, I14, I23, I32 and I41) go both ways, and each edge is the travel time in minutes.
A directed, weighted graph with 45 vertices and 88 edges.
List the intersections you can reach from I23 in the middle of town, nearest by travel time first, when most streets are one way.
From I23, closest-first visits 45 vertices, nearest first: I23, I14, I32, I22, I24, I13, I25, I31, I5, I21, and so on to I2.
Step by step
- Every distance starts at ∞, except I23, which is 0. Put I23 in the queue at 0.
- Take I23 from the front of the queue and visit it. Its distance is 0.
- I23 to I14: 0 + 3 = 3. Put I14 in the queue at 3.
- I23 to I22: 0 + 5 = 5. Put I22 in the queue at 5.
- I23 to I24: 0 + 5 = 5. Put I24 in the queue at 5.
- I23 to I32: 0 + 5 = 5. Put I32 in the queue at 5.
92 more steps lead to the last one:
- Done. Closest-first visited 45 vertices from I23, nearest first.
Use it in Go
for v, dist := range traverse.ClosestFirst(g, "I23") {
fmt.Println(v.Label(), dist)
}
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
More in Traversal
- Breadth-first: Visits vertices level by level from a start vertex.
- Depth-first: Follows one path as deep as it can, then backs up to the last vertex with a neighbor left to try, and sorts every edge it meets into four kinds.
- Random walk: Moves from a start vertex to a random out-neighbor again and again, with heavier edges more likely.