{"algorithm":"k-shortest","about":["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."],"template":{"id":"delivery-area","name":"Delivery area","description":"Eight stops in a small town. Streets are one way, and each edge is the travel time in minutes.","family":"road","directed":true,"weighted":true,"acyclic":false,"vertices":[{"id":"Depot","x":128,"y":320},{"id":"Bakery","x":352,"y":128},{"id":"Market","x":352,"y":512},{"id":"School","x":608,"y":128},{"id":"Park","x":608,"y":352},{"id":"Clinic","x":608,"y":544},{"id":"Library","x":832,"y":224},{"id":"Station","x":864,"y":480}],"edges":[{"from":"Depot","to":"Bakery","weight":4},{"from":"Depot","to":"Market","weight":2},{"from":"Market","to":"Bakery","weight":1},{"from":"Bakery","to":"School","weight":5},{"from":"Bakery","to":"Park","weight":7},{"from":"Market","to":"Park","weight":8},{"from":"Market","to":"Clinic","weight":10},{"from":"School","to":"Library","weight":3},{"from":"Park","to":"Library","weight":2},{"from":"Park","to":"Station","weight":6},{"from":"Clinic","to":"Station","weight":2},{"from":"Library","to":"Station","weight":5}],"details":{"vertices":8,"edges":12,"directed":true,"weighted":true,"acyclic":true,"weightMin":1,"weightMax":10,"negativeWeights":false,"density":0.21428571428571427,"inDegree":{"min":0,"avg":1.5,"max":3},"outDegree":{"min":0,"avg":1.5,"max":3},"selfLoops":0,"components":1}},"problem":"What are the three quickest drives from Depot to Station that don't pass the same place twice, and how much slower is each one than the first?","params":{"start":"Depot","goal":"Station","k":3},"result":{"kind":"routes","routes":[{"vertices":["Depot","Market","Clinic","Station"],"cost":14},{"vertices":["Depot","Market","Park","Station"],"cost":16},{"vertices":["Depot","Market","Bakery","Park","Station"],"cost":16}]},"answer":"The three quickest drives from Depot to Station take 14, 16 and 16 minutes. Route 2 is 2 minutes slower and shares 14% of route 1's time. Route 3 is 2 minutes slower and shares 14% of route 1's time.","legend":{"vertex":[{"id":"idle","label":"Not reached","color":"#64748B","shape":"hollow"},{"id":"done","label":"On a route found","color":"#009E73","shape":"filled"},{"id":"current","label":"Detour starts here","color":"#56B4E9","shape":"ring"},{"id":"blocked","label":"Blocked for this detour","color":"#D55E00","shape":"dashed-square"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"route-1","label":"Route 1","color":"#009E73","shape":"thick"},{"id":"route-2","label":"Route 2, where it leaves route 1","color":"#56B4E9","shape":"thick"},{"id":"route-3","label":"Route 3, where it leaves the others","color":"#E69F00","shape":"thick"},{"id":"blocked","label":"Blocked for this detour","color":"#D55E00","shape":"dotted"},{"id":"detour","label":"Detour found","color":"#CC79A7","shape":"dashed"}],"panels":[{"id":"candidates","title":"Candidates, quickest first","kind":"list"},{"id":"routes","title":"Routes found","kind":"list"},{"id":"numbers","title":"So far","kind":"numbers"}]},"steps":[{"say":"First, one search backward from Station finds the exact time to it from each of the 8 vertices Depot reaches: 8 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."},{"say":"An A* search from Depot finds the quickest route, 14 minutes, after taking 4 vertices from its queue. It is the first candidate.","ops":[{"panel":"candidates","list":[{"key":"From Depot","note":"14 min"}]},{"panel":"numbers","set":{"Routes found":"0"}},{"panel":"numbers","set":{"Candidates waiting":"1"}},{"panel":"numbers","set":{"Route 1":"–"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Route 1 is the quickest candidate: 14 minutes.","ops":[{"e":["Depot","Market"],"state":"route-1"},{"e":["Market","Clinic"],"state":"route-1"},{"e":["Clinic","Station"],"state":"route-1"},{"v":"Depot","state":"done"},{"v":"Market","state":"done"},{"v":"Clinic","state":"done"},{"v":"Station","state":"done"},{"panel":"candidates","list":[]},{"panel":"routes","list":[{"key":"Route 1","note":"14 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"0"}},{"panel":"numbers","set":{"Route 1":"14 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from Depot: block Depot to Market, the road the route takes from here. An A* search from Depot, at 0 minutes so far, takes 4 vertices from its queue and finds a way around: a candidate of 17 minutes.","ops":[{"v":"Depot","state":"current"},{"e":["Depot","Market"],"state":"blocked"},{"e":["Depot","Bakery"],"state":"detour"},{"e":["Bakery","Park"],"state":"detour"},{"e":["Park","Station"],"state":"detour"},{"panel":"candidates","list":[{"key":"From Depot","note":"17 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"1"}},{"panel":"numbers","set":{"Route 1":"14 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from Market: block Market to Clinic, the road the route takes from here, and Depot before Market so the detour can't loop back. An A* search from Market, at 2 minutes so far, takes 3 vertices from its queue and finds a way around: a candidate of 16 minutes.","ops":[{"v":"Depot","state":"done"},{"e":["Depot","Market"],"state":"route-1"},{"e":["Depot","Bakery"],"state":"idle"},{"e":["Bakery","Park"],"state":"idle"},{"e":["Park","Station"],"state":"idle"},{"v":"Market","state":"current"},{"v":"Depot","state":"blocked"},{"e":["Market","Clinic"],"state":"blocked"},{"e":["Market","Park"],"state":"detour"},{"e":["Park","Station"],"state":"detour"},{"panel":"candidates","list":[{"key":"From Market","note":"16 min"},{"key":"From Depot","note":"17 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"2"}},{"panel":"numbers","set":{"Route 1":"14 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from Clinic: block Clinic to Station, the road the route takes from here, and Depot and Market before Clinic so the detour can't loop back. An A* search from Clinic, at 12 minutes so far, takes 1 vertex from its queue and finds no way around quicker than the slowest candidate kept, 17.","ops":[{"v":"Market","state":"done"},{"v":"Depot","state":"done"},{"e":["Market","Clinic"],"state":"route-1"},{"e":["Market","Park"],"state":"idle"},{"e":["Park","Station"],"state":"idle"},{"v":"Clinic","state":"current"},{"v":"Market","state":"blocked"},{"v":"Depot","state":"blocked"},{"e":["Clinic","Station"],"state":"blocked"},{"panel":"candidates","list":[{"key":"From Market","note":"16 min"},{"key":"From Depot","note":"17 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"2"}},{"panel":"numbers","set":{"Route 1":"14 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Route 2 is the quickest candidate: 16 minutes, 2 minutes slower than route 1, sharing 14% of its time.","ops":[{"v":"Clinic","state":"done"},{"v":"Market","state":"done"},{"v":"Depot","state":"done"},{"e":["Clinic","Station"],"state":"route-1"},{"e":["Market","Park"],"state":"route-2"},{"e":["Park","Station"],"state":"route-2"},{"v":"Depot","state":"done"},{"v":"Market","state":"done"},{"v":"Park","state":"done"},{"v":"Station","state":"done"},{"panel":"candidates","list":[{"key":"From Depot","note":"17 min"}]},{"panel":"routes","list":[{"key":"Route 1","note":"14 min"},{"key":"Route 2","note":"16 min"}]},{"panel":"numbers","set":{"Routes found":"2"}},{"panel":"numbers","set":{"Candidates waiting":"1"}},{"panel":"numbers","set":{"Route 1":"14 min"}},{"panel":"numbers","set":{"Route 2":"16 min, shares 14%"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Route 2 left the route it came from at Market, so its detours start there. The vertices before it were searched for the earlier route."},{"say":"Detour from Market: block Market to Park and Market to Clinic, the roads the routes so far take from here, and Depot before Market so the detour can't loop back. An A* search from Market, at 2 minutes so far, takes 4 vertices from its queue and finds a way around: a candidate of 16 minutes. Only 1 candidate can still be used, so drop the slowest, 17 minutes.","ops":[{"v":"Market","state":"current"},{"v":"Depot","state":"blocked"},{"e":["Market","Park"],"state":"blocked"},{"e":["Market","Clinic"],"state":"blocked"},{"e":["Market","Bakery"],"state":"detour"},{"e":["Bakery","Park"],"state":"detour"},{"e":["Park","Station"],"state":"detour"},{"panel":"candidates","list":[{"key":"From Market","note":"16 min"}]},{"panel":"numbers","set":{"Routes found":"2"}},{"panel":"numbers","set":{"Candidates waiting":"1"}},{"panel":"numbers","set":{"Route 1":"14 min"}},{"panel":"numbers","set":{"Route 2":"16 min, shares 14%"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from Park: the route up to Park takes 10 minutes, and the quickest time on from Park is 6, so the best detour would be 16. That's no quicker than the slowest candidate kept, 16, so skip it.","ops":[{"v":"Market","state":"done"},{"v":"Depot","state":"done"},{"e":["Market","Park"],"state":"route-2"},{"e":["Market","Clinic"],"state":"route-1"},{"e":["Market","Bakery"],"state":"idle"},{"e":["Bakery","Park"],"state":"idle"},{"e":["Park","Station"],"state":"route-2"},{"v":"Park","state":"current"}]},{"say":"Route 3 is the quickest candidate: 16 minutes, 2 minutes slower than route 1, sharing 14% of its time.","ops":[{"v":"Park","state":"done"},{"e":["Market","Bakery"],"state":"route-3"},{"e":["Bakery","Park"],"state":"route-3"},{"v":"Depot","state":"done"},{"v":"Market","state":"done"},{"v":"Bakery","state":"done"},{"v":"Park","state":"done"},{"v":"Station","state":"done"},{"panel":"candidates","list":[]},{"panel":"routes","list":[{"key":"Route 1","note":"14 min"},{"key":"Route 2","note":"16 min"},{"key":"Route 3","note":"16 min"}]},{"panel":"numbers","set":{"Routes found":"3"}},{"panel":"numbers","set":{"Candidates waiting":"0"}},{"panel":"numbers","set":{"Route 1":"14 min"}},{"panel":"numbers","set":{"Route 2":"16 min, shares 14%"}},{"panel":"numbers","set":{"Route 3":"16 min, shares 14%"}}]},{"say":"Done. The three quickest routes take 14, 16 and 16 minutes."}],"traceNote":"","verification":"The steps come from a step-by-step copy of the algorithm. Its result is checked against gograph's on every start.","snippet":"routes, err := path.KShortest(g, \"Depot\", \"Station\", 3, nil)\nif err != nil {\n\treturn err\n}\nfor _, route := range routes {\n\tminutes := 0.0\n\tfor i := 1; i < len(route); i++ {\n\t\tminutes += g.GetEdge(route[i-1], route[i]).Weight()\n\t}\n\tfmt.Println(minutes, len(route))\n}"}
