{"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":"downtown-grid","name":"Downtown grid","description":"Twenty intersections on a downtown street grid. Streets go both ways, Market is closed to cars between 2nd and 3rd, and each edge is the travel time in minutes.","family":"road","directed":true,"weighted":true,"acyclic":false,"vertices":[{"id":"Pine & 1st","x":76,"y":156},{"id":"Pine & 2nd","x":283,"y":188},{"id":"Pine & 3rd","x":496,"y":189},{"id":"Pine & 4th","x":706,"y":160},{"id":"Pine & 5th","x":931,"y":161},{"id":"Main & 1st","x":68,"y":383},{"id":"Main & 2nd","x":268,"y":404},{"id":"Main & 3rd","x":518,"y":374},{"id":"Main & 4th","x":739,"y":393},{"id":"Main & 5th","x":946,"y":381},{"id":"Market & 1st","x":73,"y":597},{"id":"Market & 2nd","x":276,"y":620},{"id":"Market & 3rd","x":512,"y":609},{"id":"Market & 4th","x":704,"y":593},{"id":"Market & 5th","x":958,"y":591},{"id":"River & 1st","x":53,"y":842},{"id":"River & 2nd","x":274,"y":833},{"id":"River & 3rd","x":489,"y":826},{"id":"River & 4th","x":701,"y":833},{"id":"River & 5th","x":950,"y":829}],"edges":[{"from":"Pine & 1st","to":"Pine & 2nd","weight":2},{"from":"Pine & 2nd","to":"Pine & 1st","weight":2},{"from":"Pine & 1st","to":"Main & 1st","weight":2},{"from":"Main & 1st","to":"Pine & 1st","weight":2},{"from":"Pine & 2nd","to":"Pine & 3rd","weight":3},{"from":"Pine & 3rd","to":"Pine & 2nd","weight":3},{"from":"Pine & 2nd","to":"Main & 2nd","weight":3},{"from":"Main & 2nd","to":"Pine & 2nd","weight":3},{"from":"Pine & 3rd","to":"Pine & 4th","weight":2},{"from":"Pine & 4th","to":"Pine & 3rd","weight":2},{"from":"Pine & 3rd","to":"Main & 3rd","weight":2},{"from":"Main & 3rd","to":"Pine & 3rd","weight":2},{"from":"Pine & 4th","to":"Pine & 5th","weight":3},{"from":"Pine & 5th","to":"Pine & 4th","weight":3},{"from":"Pine & 4th","to":"Main & 4th","weight":2},{"from":"Main & 4th","to":"Pine & 4th","weight":2},{"from":"Pine & 5th","to":"Main & 5th","weight":3},{"from":"Main & 5th","to":"Pine & 5th","weight":3},{"from":"Main & 1st","to":"Main & 2nd","weight":3},{"from":"Main & 2nd","to":"Main & 1st","weight":3},{"from":"Main & 1st","to":"Market & 1st","weight":3},{"from":"Market & 1st","to":"Main & 1st","weight":3},{"from":"Main & 2nd","to":"Main & 3rd","weight":4},{"from":"Main & 3rd","to":"Main & 2nd","weight":4},{"from":"Main & 2nd","to":"Market & 2nd","weight":2},{"from":"Market & 2nd","to":"Main & 2nd","weight":2},{"from":"Main & 3rd","to":"Main & 4th","weight":4},{"from":"Main & 4th","to":"Main & 3rd","weight":4},{"from":"Main & 3rd","to":"Market & 3rd","weight":3},{"from":"Market & 3rd","to":"Main & 3rd","weight":3},{"from":"Main & 4th","to":"Main & 5th","weight":3},{"from":"Main & 5th","to":"Main & 4th","weight":3},{"from":"Main & 4th","to":"Market & 4th","weight":2},{"from":"Market & 4th","to":"Main & 4th","weight":2},{"from":"Main & 5th","to":"Market & 5th","weight":2},{"from":"Market & 5th","to":"Main & 5th","weight":2},{"from":"Market & 1st","to":"Market & 2nd","weight":2},{"from":"Market & 2nd","to":"Market & 1st","weight":2},{"from":"Market & 1st","to":"River & 1st","weight":2},{"from":"River & 1st","to":"Market & 1st","weight":2},{"from":"Market & 2nd","to":"River & 2nd","weight":2},{"from":"River & 2nd","to":"Market & 2nd","weight":2},{"from":"Market & 3rd","to":"Market & 4th","weight":3},{"from":"Market & 4th","to":"Market & 3rd","weight":3},{"from":"Market & 3rd","to":"River & 3rd","weight":3},{"from":"River & 3rd","to":"Market & 3rd","weight":3},{"from":"Market & 4th","to":"Market & 5th","weight":2},{"from":"Market & 5th","to":"Market & 4th","weight":2},{"from":"Market & 4th","to":"River & 4th","weight":3},{"from":"River & 4th","to":"Market & 4th","weight":3},{"from":"Market & 5th","to":"River & 5th","weight":2},{"from":"River & 5th","to":"Market & 5th","weight":2},{"from":"River & 1st","to":"River & 2nd","weight":3},{"from":"River & 2nd","to":"River & 1st","weight":3},{"from":"River & 2nd","to":"River & 3rd","weight":2},{"from":"River & 3rd","to":"River & 2nd","weight":2},{"from":"River & 3rd","to":"River & 4th","weight":2},{"from":"River & 4th","to":"River & 3rd","weight":2},{"from":"River & 4th","to":"River & 5th","weight":4},{"from":"River & 5th","to":"River & 4th","weight":4}],"details":{"vertices":20,"edges":60,"directed":true,"weighted":true,"acyclic":false,"weightMin":2,"weightMax":4,"negativeWeights":false,"density":0.15789473684210525,"inDegree":{"min":2,"avg":3,"max":4},"outDegree":{"min":2,"avg":3,"max":4},"selfLoops":0,"components":1}},"problem":"What are the three quickest drives from Pine & 1st to River & 5th that don't pass the same place twice, and how much slower is each one than the first?","params":{"start":"Pine & 1st","goal":"River & 5th","k":3},"result":{"kind":"routes","routes":[{"vertices":["Pine \u0026 1st","Pine \u0026 2nd","Pine \u0026 3rd","Pine \u0026 4th","Main \u0026 4th","Market \u0026 4th","Market \u0026 5th","River \u0026 5th"],"cost":15},{"vertices":["Pine \u0026 1st","Pine \u0026 2nd","Pine \u0026 3rd","Pine \u0026 4th","Main \u0026 4th","Main \u0026 5th","Market \u0026 5th","River \u0026 5th"],"cost":16},{"vertices":["Pine \u0026 1st","Main \u0026 1st","Main \u0026 2nd","Market \u0026 2nd","River \u0026 2nd","River \u0026 3rd","River \u0026 4th","River \u0026 5th"],"cost":17}]},"answer":"The three quickest drives from Pine & 1st to River & 5th take 15, 16 and 17 minutes. Route 2 is 1 minute slower and shares 73% of route 1's time. Route 3 is 2 minutes slower and shares 0% 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 River & 5th finds the exact time to it from each of the 20 vertices Pine & 1st reaches: 20 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 Pine & 1st finds the quickest route, 15 minutes, after taking 8 vertices from its queue. It is the first candidate.","ops":[{"panel":"candidates","list":[{"key":"From Pine & 1st","note":"15 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: 15 minutes.","ops":[{"e":["Pine & 1st","Pine & 2nd"],"state":"route-1"},{"e":["Pine & 2nd","Pine & 3rd"],"state":"route-1"},{"e":["Pine & 3rd","Pine & 4th"],"state":"route-1"},{"e":["Pine & 4th","Main & 4th"],"state":"route-1"},{"e":["Main & 4th","Market & 4th"],"state":"route-1"},{"e":["Market & 4th","Market & 5th"],"state":"route-1"},{"e":["Market & 5th","River & 5th"],"state":"route-1"},{"v":"Pine & 1st","state":"done"},{"v":"Pine & 2nd","state":"done"},{"v":"Pine & 3rd","state":"done"},{"v":"Pine & 4th","state":"done"},{"v":"Main & 4th","state":"done"},{"v":"Market & 4th","state":"done"},{"v":"Market & 5th","state":"done"},{"v":"River & 5th","state":"done"},{"panel":"candidates","list":[]},{"panel":"routes","list":[{"key":"Route 1","note":"15 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"0"}},{"panel":"numbers","set":{"Route 1":"15 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from Pine & 1st: block Pine & 1st to Pine & 2nd, the road the route takes from here. An A* search from Pine & 1st, at 0 minutes so far, takes 8 vertices from its queue and finds a way around: a candidate of 17 minutes.","ops":[{"v":"Pine & 1st","state":"current"},{"e":["Pine & 1st","Pine & 2nd"],"state":"blocked"},{"e":["Pine & 1st","Main & 1st"],"state":"detour"},{"e":["Main & 1st","Main & 2nd"],"state":"detour"},{"e":["Main & 2nd","Market & 2nd"],"state":"detour"},{"e":["Market & 2nd","River & 2nd"],"state":"detour"},{"e":["River & 2nd","River & 3rd"],"state":"detour"},{"e":["River & 3rd","River & 4th"],"state":"detour"},{"e":["River & 4th","River & 5th"],"state":"detour"},{"panel":"candidates","list":[{"key":"From Pine & 1st","note":"17 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"1"}},{"panel":"numbers","set":{"Route 1":"15 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from Pine & 2nd: block Pine & 2nd to Pine & 3rd, the road the route takes from here, and Pine & 1st before Pine & 2nd so the detour can't loop back. An A* search from Pine & 2nd, at 2 minutes so far, takes 7 vertices from its queue and finds a way around: a candidate of 17 minutes.","ops":[{"v":"Pine & 1st","state":"done"},{"e":["Pine & 1st","Pine & 2nd"],"state":"route-1"},{"e":["Pine & 1st","Main & 1st"],"state":"idle"},{"e":["Main & 1st","Main & 2nd"],"state":"idle"},{"e":["Main & 2nd","Market & 2nd"],"state":"idle"},{"e":["Market & 2nd","River & 2nd"],"state":"idle"},{"e":["River & 2nd","River & 3rd"],"state":"idle"},{"e":["River & 3rd","River & 4th"],"state":"idle"},{"e":["River & 4th","River & 5th"],"state":"idle"},{"v":"Pine & 2nd","state":"current"},{"v":"Pine & 1st","state":"blocked"},{"e":["Pine & 2nd","Pine & 3rd"],"state":"blocked"},{"e":["Pine & 2nd","Main & 2nd"],"state":"detour"},{"e":["Main & 2nd","Market & 2nd"],"state":"detour"},{"e":["Market & 2nd","River & 2nd"],"state":"detour"},{"e":["River & 2nd","River & 3rd"],"state":"detour"},{"e":["River & 3rd","River & 4th"],"state":"detour"},{"e":["River & 4th","River & 5th"],"state":"detour"},{"panel":"candidates","list":[{"key":"From Pine & 1st","note":"17 min"},{"key":"From Pine & 2nd","note":"17 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"2"}},{"panel":"numbers","set":{"Route 1":"15 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from Pine & 3rd: block Pine & 3rd to Pine & 4th, the road the route takes from here, and Pine & 1st and Pine & 2nd before Pine & 3rd so the detour can't loop back. An A* search from Pine & 3rd, at 5 minutes so far, takes 2 vertices from its queue and finds no way around quicker than the slowest candidate kept, 17.","ops":[{"v":"Pine & 2nd","state":"done"},{"v":"Pine & 1st","state":"done"},{"e":["Pine & 2nd","Pine & 3rd"],"state":"route-1"},{"e":["Pine & 2nd","Main & 2nd"],"state":"idle"},{"e":["Main & 2nd","Market & 2nd"],"state":"idle"},{"e":["Market & 2nd","River & 2nd"],"state":"idle"},{"e":["River & 2nd","River & 3rd"],"state":"idle"},{"e":["River & 3rd","River & 4th"],"state":"idle"},{"e":["River & 4th","River & 5th"],"state":"idle"},{"v":"Pine & 3rd","state":"current"},{"v":"Pine & 2nd","state":"blocked"},{"v":"Pine & 1st","state":"blocked"},{"e":["Pine & 3rd","Pine & 4th"],"state":"blocked"},{"panel":"candidates","list":[{"key":"From Pine & 1st","note":"17 min"},{"key":"From Pine & 2nd","note":"17 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"2"}},{"panel":"numbers","set":{"Route 1":"15 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from Pine & 4th: block Pine & 4th to Main & 4th, the road the route takes from here, and Pine & 1st, Pine & 2nd and Pine & 3rd before Pine & 4th so the detour can't loop back. An A* search from Pine & 4th, at 7 minutes so far, takes 2 vertices from its queue and finds no way around quicker than the slowest candidate kept, 17.","ops":[{"v":"Pine & 3rd","state":"done"},{"v":"Pine & 2nd","state":"done"},{"v":"Pine & 1st","state":"done"},{"e":["Pine & 3rd","Pine & 4th"],"state":"route-1"},{"v":"Pine & 4th","state":"current"},{"v":"Pine & 2nd","state":"blocked"},{"v":"Pine & 3rd","state":"blocked"},{"v":"Pine & 1st","state":"blocked"},{"e":["Pine & 4th","Main & 4th"],"state":"blocked"},{"panel":"candidates","list":[{"key":"From Pine & 1st","note":"17 min"},{"key":"From Pine & 2nd","note":"17 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"2"}},{"panel":"numbers","set":{"Route 1":"15 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from Main & 4th: block Main & 4th to Market & 4th, the road the route takes from here, and the 4 vertices before Main & 4th so the detour can't loop back. An A* search from Main & 4th, at 9 minutes so far, takes 4 vertices from its queue and finds a way around: a candidate of 16 minutes. Only 2 candidates can still be used, so drop the slowest, 17 minutes.","ops":[{"v":"Pine & 4th","state":"done"},{"v":"Pine & 2nd","state":"done"},{"v":"Pine & 3rd","state":"done"},{"v":"Pine & 1st","state":"done"},{"e":["Pine & 4th","Main & 4th"],"state":"route-1"},{"v":"Main & 4th","state":"current"},{"v":"Pine & 2nd","state":"blocked"},{"v":"Pine & 3rd","state":"blocked"},{"v":"Pine & 4th","state":"blocked"},{"v":"Pine & 1st","state":"blocked"},{"e":["Main & 4th","Market & 4th"],"state":"blocked"},{"e":["Main & 4th","Main & 5th"],"state":"detour"},{"e":["Main & 5th","Market & 5th"],"state":"detour"},{"e":["Market & 5th","River & 5th"],"state":"detour"},{"panel":"candidates","list":[{"key":"From Main & 4th","note":"16 min"},{"key":"From Pine & 1st","note":"17 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"2"}},{"panel":"numbers","set":{"Route 1":"15 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from Market & 4th: block Market & 4th to Market & 5th, the road the route takes from here, and the 5 vertices before Market & 4th so the detour can't loop back. An A* search from Market & 4th, at 11 minutes so far, takes 2 vertices from its queue and finds no way around quicker than the slowest candidate kept, 17.","ops":[{"v":"Main & 4th","state":"done"},{"v":"Pine & 2nd","state":"done"},{"v":"Pine & 3rd","state":"done"},{"v":"Pine & 4th","state":"done"},{"v":"Pine & 1st","state":"done"},{"e":["Main & 4th","Market & 4th"],"state":"route-1"},{"e":["Main & 4th","Main & 5th"],"state":"idle"},{"e":["Main & 5th","Market & 5th"],"state":"idle"},{"e":["Market & 5th","River & 5th"],"state":"route-1"},{"v":"Market & 4th","state":"current"},{"v":"Pine & 2nd","state":"blocked"},{"v":"Pine & 3rd","state":"blocked"},{"v":"Pine & 4th","state":"blocked"},{"v":"Main & 4th","state":"blocked"},{"v":"Pine & 1st","state":"blocked"},{"e":["Market & 4th","Market & 5th"],"state":"blocked"},{"panel":"candidates","list":[{"key":"From Main & 4th","note":"16 min"},{"key":"From Pine & 1st","note":"17 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"2"}},{"panel":"numbers","set":{"Route 1":"15 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from Market & 5th: block Market & 5th to River & 5th, the road the route takes from here, and the 6 vertices before Market & 5th so the detour can't loop back. An A* search from Market & 5th, at 13 minutes so far, takes 2 vertices from its queue and finds no way around quicker than the slowest candidate kept, 17.","ops":[{"v":"Market & 4th","state":"done"},{"v":"Pine & 2nd","state":"done"},{"v":"Pine & 3rd","state":"done"},{"v":"Pine & 4th","state":"done"},{"v":"Main & 4th","state":"done"},{"v":"Pine & 1st","state":"done"},{"e":["Market & 4th","Market & 5th"],"state":"route-1"},{"v":"Market & 5th","state":"current"},{"v":"Pine & 2nd","state":"blocked"},{"v":"Pine & 3rd","state":"blocked"},{"v":"Pine & 4th","state":"blocked"},{"v":"Main & 4th","state":"blocked"},{"v":"Market & 4th","state":"blocked"},{"v":"Pine & 1st","state":"blocked"},{"e":["Market & 5th","River & 5th"],"state":"blocked"},{"panel":"candidates","list":[{"key":"From Main & 4th","note":"16 min"},{"key":"From Pine & 1st","note":"17 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"2"}},{"panel":"numbers","set":{"Route 1":"15 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Route 2 is the quickest candidate: 16 minutes, 1 minute slower than route 1, sharing 73% of its time.","ops":[{"v":"Market & 5th","state":"done"},{"v":"Pine & 2nd","state":"done"},{"v":"Pine & 3rd","state":"done"},{"v":"Pine & 4th","state":"done"},{"v":"Main & 4th","state":"done"},{"v":"Market & 4th","state":"done"},{"v":"Pine & 1st","state":"done"},{"e":["Market & 5th","River & 5th"],"state":"route-1"},{"e":["Main & 4th","Main & 5th"],"state":"route-2"},{"e":["Main & 5th","Market & 5th"],"state":"route-2"},{"v":"Pine & 1st","state":"done"},{"v":"Pine & 2nd","state":"done"},{"v":"Pine & 3rd","state":"done"},{"v":"Pine & 4th","state":"done"},{"v":"Main & 4th","state":"done"},{"v":"Main & 5th","state":"done"},{"v":"Market & 5th","state":"done"},{"v":"River & 5th","state":"done"},{"panel":"candidates","list":[{"key":"From Pine & 1st","note":"17 min"}]},{"panel":"routes","list":[{"key":"Route 1","note":"15 min"},{"key":"Route 2","note":"16 min"}]},{"panel":"numbers","set":{"Routes found":"2"}},{"panel":"numbers","set":{"Candidates waiting":"1"}},{"panel":"numbers","set":{"Route 1":"15 min"}},{"panel":"numbers","set":{"Route 2":"16 min, shares 73%"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Route 2 left the route it came from at Main & 4th, so its detours start there. The vertices before it were searched for the earlier route."},{"say":"Detour from Main & 4th: block Main & 4th to Main & 5th and Main & 4th to Market & 4th, the roads the routes so far take from here, and the 4 vertices before Main & 4th so the detour can't loop back. An A* search from Main & 4th, at 9 minutes so far, takes 2 vertices from its queue and finds no way around quicker than the slowest candidate kept, 17.","ops":[{"v":"Main & 4th","state":"current"},{"v":"Pine & 2nd","state":"blocked"},{"v":"Pine & 3rd","state":"blocked"},{"v":"Pine & 4th","state":"blocked"},{"v":"Pine & 1st","state":"blocked"},{"e":["Main & 4th","Main & 5th"],"state":"blocked"},{"e":["Main & 4th","Market & 4th"],"state":"blocked"},{"panel":"candidates","list":[{"key":"From Pine & 1st","note":"17 min"}]},{"panel":"numbers","set":{"Routes found":"2"}},{"panel":"numbers","set":{"Candidates waiting":"1"}},{"panel":"numbers","set":{"Route 1":"15 min"}},{"panel":"numbers","set":{"Route 2":"16 min, shares 73%"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from Main & 5th: block Main & 5th to Market & 5th, the road the route takes from here, and the 5 vertices before Main & 5th so the detour can't loop back. An A* search from Main & 5th, at 12 minutes so far, takes 2 vertices from its queue and finds no way around quicker than the slowest candidate kept, 17.","ops":[{"v":"Main & 4th","state":"done"},{"v":"Pine & 2nd","state":"done"},{"v":"Pine & 3rd","state":"done"},{"v":"Pine & 4th","state":"done"},{"v":"Pine & 1st","state":"done"},{"e":["Main & 4th","Main & 5th"],"state":"route-2"},{"e":["Main & 4th","Market & 4th"],"state":"route-1"},{"v":"Main & 5th","state":"current"},{"v":"Pine & 2nd","state":"blocked"},{"v":"Pine & 3rd","state":"blocked"},{"v":"Pine & 4th","state":"blocked"},{"v":"Main & 4th","state":"blocked"},{"v":"Pine & 1st","state":"blocked"},{"e":["Main & 5th","Market & 5th"],"state":"blocked"},{"panel":"candidates","list":[{"key":"From Pine & 1st","note":"17 min"}]},{"panel":"numbers","set":{"Routes found":"2"}},{"panel":"numbers","set":{"Candidates waiting":"1"}},{"panel":"numbers","set":{"Route 1":"15 min"}},{"panel":"numbers","set":{"Route 2":"16 min, shares 73%"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from Market & 5th: block Market & 5th to River & 5th, the road the route takes from here, and the 6 vertices before Market & 5th so the detour can't loop back. An A* search from Market & 5th, at 14 minutes so far, takes 2 vertices from its queue and finds no way around quicker than the slowest candidate kept, 17.","ops":[{"v":"Main & 5th","state":"done"},{"v":"Pine & 2nd","state":"done"},{"v":"Pine & 3rd","state":"done"},{"v":"Pine & 4th","state":"done"},{"v":"Main & 4th","state":"done"},{"v":"Pine & 1st","state":"done"},{"e":["Main & 5th","Market & 5th"],"state":"route-2"},{"v":"Market & 5th","state":"current"},{"v":"Pine & 2nd","state":"blocked"},{"v":"Pine & 3rd","state":"blocked"},{"v":"Pine & 4th","state":"blocked"},{"v":"Main & 4th","state":"blocked"},{"v":"Main & 5th","state":"blocked"},{"v":"Pine & 1st","state":"blocked"},{"e":["Market & 5th","River & 5th"],"state":"blocked"},{"panel":"candidates","list":[{"key":"From Pine & 1st","note":"17 min"}]},{"panel":"numbers","set":{"Routes found":"2"}},{"panel":"numbers","set":{"Candidates waiting":"1"}},{"panel":"numbers","set":{"Route 1":"15 min"}},{"panel":"numbers","set":{"Route 2":"16 min, shares 73%"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Route 3 is the quickest candidate: 17 minutes, 2 minutes slower than route 1, sharing 0% of its time.","ops":[{"v":"Market & 5th","state":"done"},{"v":"Pine & 2nd","state":"done"},{"v":"Pine & 3rd","state":"done"},{"v":"Pine & 4th","state":"done"},{"v":"Main & 4th","state":"done"},{"v":"Main & 5th","state":"done"},{"v":"Pine & 1st","state":"done"},{"e":["Market & 5th","River & 5th"],"state":"route-1"},{"e":["Pine & 1st","Main & 1st"],"state":"route-3"},{"e":["Main & 1st","Main & 2nd"],"state":"route-3"},{"e":["Main & 2nd","Market & 2nd"],"state":"route-3"},{"e":["Market & 2nd","River & 2nd"],"state":"route-3"},{"e":["River & 2nd","River & 3rd"],"state":"route-3"},{"e":["River & 3rd","River & 4th"],"state":"route-3"},{"e":["River & 4th","River & 5th"],"state":"route-3"},{"v":"Pine & 1st","state":"done"},{"v":"Main & 1st","state":"done"},{"v":"Main & 2nd","state":"done"},{"v":"Market & 2nd","state":"done"},{"v":"River & 2nd","state":"done"},{"v":"River & 3rd","state":"done"},{"v":"River & 4th","state":"done"},{"v":"River & 5th","state":"done"},{"panel":"candidates","list":[]},{"panel":"routes","list":[{"key":"Route 1","note":"15 min"},{"key":"Route 2","note":"16 min"},{"key":"Route 3","note":"17 min"}]},{"panel":"numbers","set":{"Routes found":"3"}},{"panel":"numbers","set":{"Candidates waiting":"0"}},{"panel":"numbers","set":{"Route 1":"15 min"}},{"panel":"numbers","set":{"Route 2":"16 min, shares 73%"}},{"panel":"numbers","set":{"Route 3":"17 min, shares 0%"}}]},{"say":"Done. The three quickest routes take 15, 16 and 17 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, \"Pine & 1st\", \"River & 5th\", 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}"}
