k shortest paths
Finds the k quickest routes from one vertex to another that don't repeat a vertex, quickest first, the way a navigation app offers a few routes.
Time complexity O(k·V·(V+E) log V), gograph function path.KShortest.
How it works
A navigation app rarely shows one route. It offers the quickest and two or three others that aren't much slower, so the driver can avoid a bridge or a busy street. Yen's algorithm finds the k quickest routes that don't repeat a vertex. It takes the quickest route, then at each vertex along it blocks the road that route takes from there, and the roads the routes found before take from the same start of the route, and finds the quickest way around. Each way around is a candidate, and the quickest candidate is the next route.
gograph runs it with Lawler's change: a route only branches from the vertex where it left the route it came from, so the vertices before that are never searched again and no route is found twice. It keeps at most k-1 candidates, since no more can be used, and skips a detour that can't beat the slowest of them.
Each detour search is A* guided by the exact time from each vertex to the goal, found once by one backward search at the start. Blocking roads only makes routes slower, so that guess never says more than the time left. Time is O(k·V·(V+E) log V) in the worst case, and the detours stay short in practice.
path.KShortest returns the routes without their costs, so the page adds up the minutes itself. Fewer than k routes is not an error, and k below 1 returns ErrInvalidK. On a street grid, many of the quickest routes differ by a single block, so the page shows how much of each route it shares with the first.
Rasht streets
The main streets of Rasht in northern Iran, from OpenStreetMap, with the Gohar Roud and Zar Joub rivers running through the city. Each intersection is named after its streets in English, one-way streets go one way, and each edge is the minutes to drive it at the speed limit, or at 22 to 40 km/h by road type where the map has no limit.
A directed, weighted graph with 298 vertices and 568 edges.
Map data © OpenStreetMap contributors.
What are the three quickest drives from Gomnam Underpass & Gomnam Sq to Zar Joub Sq & Shariati Blvd that don't pass the same place twice, and how much slower is each one than the first?
The three quickest drives from Gomnam Underpass & Gomnam Sq to Zar Joub Sq & Shariati Blvd take 8.81, 8.92 and 9.41 minutes. Route 2 is 0.11 minutes slower and shares 94% of route 1's time. Route 3 is 0.6 minutes slower and shares 65% of route 1's time.
Step by step
- First, one search backward from Zar Joub Sq & Shariati Blvd finds the exact time to it from each of the 298 vertices Gomnam Underpass & Gomnam Sq reaches: 298 of them can get there. Each detour search uses that time as its guess, and blocking roads only makes routes slower, so the guess never says more than the time left.
- An A* search from Gomnam Underpass & Gomnam Sq finds the quickest route, 8.81 minutes, after taking 24 vertices from its queue. It is the first candidate.
- Route 1 is the quickest candidate: 8.81 minutes.
- Detour from Gomnam Underpass & Gomnam Sq: block Gomnam Underpass & Gomnam Sq to Taleghani Frontage Rd near Gomnam Bridge (S), the road the route takes from here. An A* search from Gomnam Underpass & Gomnam Sq, at 0 minutes so far, takes 24 vertices from its queue and finds a way around: a candidate of 8.92 minutes.
- Detour from Taleghani Frontage Rd near Gomnam Bridge (S): block Taleghani Frontage Rd near Gomnam Bridge (S) to Gomnam Bridge & Taleghani Ave, the road the route takes from here, and Gomnam Underpass & Gomnam Sq before Taleghani Frontage Rd near Gomnam Bridge (S) so the detour can't loop back. An A* search from Taleghani Frontage Rd near Gomnam Bridge (S), at 0.12 minutes so far, takes 1 vertex from its queue and finds no way around.
- Detour from Gomnam Bridge & Taleghani Ave: block Gomnam Bridge & Taleghani Ave to Taleghani Ave & Zamen St, the road the route takes from here, and Gomnam Underpass & Gomnam Sq and Taleghani Frontage Rd near Gomnam Bridge (S) before Gomnam Bridge & Taleghani Ave so the detour can't loop back. An A* search from Gomnam Bridge & Taleghani Ave, at 0.5 minutes so far, takes 36 vertices from its queue and finds a way around: a candidate of 11.44 minutes.
45 more steps lead to the last one:
- Done. The three quickest routes take 8.81, 8.92 and 9.41 minutes.
Use it in Go
routes, err := path.KShortest(g, "Gomnam Underpass & Gomnam Sq", "Zar Joub Sq & Shariati Blvd", 3, nil)
if err != nil {
return err
}
for _, route := range routes {
minutes := 0.0
for i := 1; i < len(route); i++ {
minutes += g.GetEdge(route[i-1], route[i]).Weight()
}
fmt.Println(minutes, len(route))
}
Example graphs
- New York streets, 295 vertices and 669 edges
- London streets, 274 vertices and 598 edges
- San Francisco streets, 248 vertices and 548 edges
- Rasht streets, 298 vertices and 568 edges
- 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 Shortest paths
- Dijkstra: Finds the shortest distance from a start vertex to every other vertex when no edge weight is negative.
- A*: Finds the quickest route from one vertex to another, looking first where a guess of the time left says the goal is, so it settles far fewer vertices than Dijkstra.
- Bidirectional search: Finds the quickest route from one vertex to another by searching forward from the start and backward from the goal at once, until the two searches meet.
- Beam search: Looks for a route from one vertex to another while keeping only the few best partial paths at each step, so its memory and time stay bounded, at the cost of sometimes missing the best route.
- Multi-source Dijkstra: Finds the nearest of several sources for every vertex, and the distance from it, in one search.
- k-center: Chooses k centers so that the vertex farthest from its nearest center is as near as it can make it.
- Bellman-Ford: Finds the shortest distance from a start vertex to every other vertex, even with negative weights, and reports a negative cycle when the start can reach one.
- Floyd-Warshall: Finds the shortest distance between every pair of vertices, even with negative weights, by letting paths stop at one more vertex in each round.