{"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":"school-run","name":"School run","description":"Six places on the morning drive to school. Most streets go both ways, and each edge is the travel time in minutes.","family":"road","directed":true,"weighted":true,"acyclic":false,"vertices":[{"id":"Home","x":128,"y":320},{"id":"Bakery","x":352,"y":160},{"id":"Bridge","x":352,"y":480},{"id":"Park","x":608,"y":320},{"id":"Library","x":832,"y":160},{"id":"School","x":864,"y":448}],"edges":[{"from":"Home","to":"Bakery","weight":4},{"from":"Bakery","to":"Home","weight":4},{"from":"Home","to":"Bridge","weight":3},{"from":"Bridge","to":"Home","weight":3},{"from":"Bakery","to":"Park","weight":3},{"from":"Park","to":"Bakery","weight":3},{"from":"Bridge","to":"Park","weight":2},{"from":"Park","to":"Bridge","weight":2},{"from":"Park","to":"Library","weight":4},{"from":"Library","to":"Park","weight":4},{"from":"Park","to":"School","weight":7},{"from":"Library","to":"School","weight":2},{"from":"School","to":"Library","weight":2}],"details":{"vertices":6,"edges":13,"directed":true,"weighted":true,"acyclic":false,"weightMin":2,"weightMax":7,"negativeWeights":false,"density":0.43333333333333335,"inDegree":{"min":2,"avg":2.1666666666666665,"max":3},"outDegree":{"min":1,"avg":2.1666666666666665,"max":4},"selfLoops":0,"components":1}},"problem":"What are the three quickest drives from Home to School that don't pass the same place twice, and how much slower is each one than the first?","params":{"start":"Home","goal":"School","k":3},"result":{"kind":"routes","routes":[{"vertices":["Home","Bridge","Park","Library","School"],"cost":11},{"vertices":["Home","Bridge","Park","School"],"cost":12},{"vertices":["Home","Bakery","Park","Library","School"],"cost":13}]},"answer":"The three quickest drives from Home to School take 11, 12 and 13 minutes. Route 2 is 1 minute slower and shares 45% of route 1's time. Route 3 is 2 minutes slower and shares 55% 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 School finds the exact time to it from each of the 6 vertices Home reaches: 6 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 Home finds the quickest route, 11 minutes, after taking 5 vertices from its queue. It is the first candidate.","ops":[{"panel":"candidates","list":[{"key":"From Home","note":"11 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: 11 minutes.","ops":[{"e":["Home","Bridge"],"state":"route-1"},{"e":["Bridge","Park"],"state":"route-1"},{"e":["Park","Library"],"state":"route-1"},{"e":["Library","School"],"state":"route-1"},{"v":"Home","state":"done"},{"v":"Bridge","state":"done"},{"v":"Park","state":"done"},{"v":"Library","state":"done"},{"v":"School","state":"done"},{"panel":"candidates","list":[]},{"panel":"routes","list":[{"key":"Route 1","note":"11 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"0"}},{"panel":"numbers","set":{"Route 1":"11 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from Home: block Home to Bridge, the road the route takes from here. An A* search from Home, at 0 minutes so far, takes 5 vertices from its queue and finds a way around: a candidate of 13 minutes.","ops":[{"v":"Home","state":"current"},{"e":["Home","Bridge"],"state":"blocked"},{"e":["Home","Bakery"],"state":"detour"},{"e":["Bakery","Park"],"state":"detour"},{"e":["Park","Library"],"state":"detour"},{"e":["Library","School"],"state":"detour"},{"panel":"candidates","list":[{"key":"From Home","note":"13 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"1"}},{"panel":"numbers","set":{"Route 1":"11 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from Bridge: block Bridge to Park, the road the route takes from here, and Home before Bridge so the detour can't loop back. An A* search from Bridge, at 3 minutes so far, takes 1 vertex from its queue and finds no way around.","ops":[{"v":"Home","state":"done"},{"e":["Home","Bridge"],"state":"route-1"},{"e":["Home","Bakery"],"state":"idle"},{"e":["Bakery","Park"],"state":"idle"},{"e":["Park","Library"],"state":"route-1"},{"e":["Library","School"],"state":"route-1"},{"v":"Bridge","state":"current"},{"v":"Home","state":"blocked"},{"e":["Bridge","Park"],"state":"blocked"},{"panel":"candidates","list":[{"key":"From Home","note":"13 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"1"}},{"panel":"numbers","set":{"Route 1":"11 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from Park: block Park to Library, the road the route takes from here, and Home and Bridge before Park so the detour can't loop back. An A* search from Park, at 5 minutes so far, takes 2 vertices from its queue and finds a way around: a candidate of 12 minutes.","ops":[{"v":"Bridge","state":"done"},{"v":"Home","state":"done"},{"e":["Bridge","Park"],"state":"route-1"},{"v":"Park","state":"current"},{"v":"Bridge","state":"blocked"},{"v":"Home","state":"blocked"},{"e":["Park","Library"],"state":"blocked"},{"e":["Park","School"],"state":"detour"},{"panel":"candidates","list":[{"key":"From Park","note":"12 min"},{"key":"From Home","note":"13 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"2"}},{"panel":"numbers","set":{"Route 1":"11 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from Library: block Library to School, the road the route takes from here, and Home, Bridge and Park before Library so the detour can't loop back. An A* search from Library, at 9 minutes so far, takes 1 vertex from its queue and finds no way around quicker than the slowest candidate kept, 13.","ops":[{"v":"Park","state":"done"},{"v":"Bridge","state":"done"},{"v":"Home","state":"done"},{"e":["Park","Library"],"state":"route-1"},{"e":["Park","School"],"state":"idle"},{"v":"Library","state":"current"},{"v":"Bridge","state":"blocked"},{"v":"Park","state":"blocked"},{"v":"Home","state":"blocked"},{"e":["Library","School"],"state":"blocked"},{"panel":"candidates","list":[{"key":"From Park","note":"12 min"},{"key":"From Home","note":"13 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"2"}},{"panel":"numbers","set":{"Route 1":"11 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Route 2 is the quickest candidate: 12 minutes, 1 minute slower than route 1, sharing 45% of its time.","ops":[{"v":"Library","state":"done"},{"v":"Bridge","state":"done"},{"v":"Park","state":"done"},{"v":"Home","state":"done"},{"e":["Library","School"],"state":"route-1"},{"e":["Park","School"],"state":"route-2"},{"v":"Home","state":"done"},{"v":"Bridge","state":"done"},{"v":"Park","state":"done"},{"v":"School","state":"done"},{"panel":"candidates","list":[{"key":"From Home","note":"13 min"}]},{"panel":"routes","list":[{"key":"Route 1","note":"11 min"},{"key":"Route 2","note":"12 min"}]},{"panel":"numbers","set":{"Routes found":"2"}},{"panel":"numbers","set":{"Candidates waiting":"1"}},{"panel":"numbers","set":{"Route 1":"11 min"}},{"panel":"numbers","set":{"Route 2":"12 min, shares 45%"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Route 2 left the route it came from at Park, so its detours start there. The vertices before it were searched for the earlier route."},{"say":"Detour from Park: block Park to School and Park to Library, the roads the routes so far take from here, and Home and Bridge before Park so the detour can't loop back. An A* search from Park, at 5 minutes so far, takes 2 vertices from its queue and finds no way around quicker than the slowest candidate kept, 13.","ops":[{"v":"Park","state":"current"},{"v":"Bridge","state":"blocked"},{"v":"Home","state":"blocked"},{"e":["Park","School"],"state":"blocked"},{"e":["Park","Library"],"state":"blocked"},{"panel":"candidates","list":[{"key":"From Home","note":"13 min"}]},{"panel":"numbers","set":{"Routes found":"2"}},{"panel":"numbers","set":{"Candidates waiting":"1"}},{"panel":"numbers","set":{"Route 1":"11 min"}},{"panel":"numbers","set":{"Route 2":"12 min, shares 45%"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Route 3 is the quickest candidate: 13 minutes, 2 minutes slower than route 1, sharing 55% of its time.","ops":[{"v":"Park","state":"done"},{"v":"Bridge","state":"done"},{"v":"Home","state":"done"},{"e":["Park","School"],"state":"route-2"},{"e":["Park","Library"],"state":"route-1"},{"e":["Home","Bakery"],"state":"route-3"},{"e":["Bakery","Park"],"state":"route-3"},{"v":"Home","state":"done"},{"v":"Bakery","state":"done"},{"v":"Park","state":"done"},{"v":"Library","state":"done"},{"v":"School","state":"done"},{"panel":"candidates","list":[]},{"panel":"routes","list":[{"key":"Route 1","note":"11 min"},{"key":"Route 2","note":"12 min"},{"key":"Route 3","note":"13 min"}]},{"panel":"numbers","set":{"Routes found":"3"}},{"panel":"numbers","set":{"Candidates waiting":"0"}},{"panel":"numbers","set":{"Route 1":"11 min"}},{"panel":"numbers","set":{"Route 2":"12 min, shares 45%"}},{"panel":"numbers","set":{"Route 3":"13 min, shares 55%"}}]},{"say":"Done. The three quickest routes take 11, 12 and 13 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, \"Home\", \"School\", 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}"}
