{"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":"one-way-city","name":"One-way city","description":"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.","family":"road","directed":true,"weighted":true,"acyclic":false,"vertices":[{"id":"I1","x":64,"y":287},{"id":"I2","x":175,"y":279},{"id":"I3","x":288,"y":275},{"id":"I4","x":381,"y":280},{"id":"I5","x":500,"y":288},{"id":"I6","x":601,"y":274},{"id":"I7","x":715,"y":288},{"id":"I8","x":836,"y":273},{"id":"I9","x":947,"y":289},{"id":"I10","x":58,"y":382},{"id":"I11","x":177,"y":399},{"id":"I12","x":280,"y":398},{"id":"I13","x":395,"y":389},{"id":"I14","x":492,"y":379},{"id":"I15","x":614,"y":383},{"id":"I16","x":720,"y":392},{"id":"I17","x":833,"y":382},{"id":"I18","x":942,"y":384},{"id":"I19","x":55,"y":502},{"id":"I20","x":168,"y":497},{"id":"I21","x":282,"y":490},{"id":"I22","x":393,"y":509},{"id":"I23","x":499,"y":491},{"id":"I24","x":613,"y":508},{"id":"I25","x":714,"y":501},{"id":"I26","x":820,"y":492},{"id":"I27","x":937,"y":502},{"id":"I28","x":67,"y":610},{"id":"I29","x":171,"y":617},{"id":"I30","x":288,"y":600},{"id":"I31","x":392,"y":611},{"id":"I32","x":510,"y":613},{"id":"I33","x":605,"y":600},{"id":"I34","x":725,"y":611},{"id":"I35","x":839,"y":607},{"id":"I36","x":938,"y":605},{"id":"I37","x":56,"y":719},{"id":"I38","x":171,"y":722},{"id":"I39","x":283,"y":728},{"id":"I40","x":391,"y":711},{"id":"I41","x":510,"y":716},{"id":"I42","x":613,"y":724},{"id":"I43","x":715,"y":719},{"id":"I44","x":838,"y":712},{"id":"I45","x":943,"y":720}],"edges":[{"from":"I1","to":"I2","weight":3},{"from":"I10","to":"I1","weight":5},{"from":"I2","to":"I3","weight":2},{"from":"I2","to":"I11","weight":4},{"from":"I3","to":"I4","weight":3},{"from":"I12","to":"I3","weight":4},{"from":"I4","to":"I5","weight":2},{"from":"I4","to":"I13","weight":2},{"from":"I5","to":"I6","weight":5},{"from":"I5","to":"I14","weight":5},{"from":"I14","to":"I5","weight":5},{"from":"I6","to":"I7","weight":4},{"from":"I15","to":"I6","weight":4},{"from":"I7","to":"I8","weight":4},{"from":"I7","to":"I16","weight":3},{"from":"I8","to":"I9","weight":4},{"from":"I17","to":"I8","weight":5},{"from":"I9","to":"I18","weight":2},{"from":"I11","to":"I10","weight":4},{"from":"I19","to":"I10","weight":5},{"from":"I12","to":"I11","weight":5},{"from":"I11","to":"I20","weight":3},{"from":"I13","to":"I12","weight":5},{"from":"I21","to":"I12","weight":2},{"from":"I14","to":"I13","weight":4},{"from":"I13","to":"I22","weight":3},{"from":"I15","to":"I14","weight":2},{"from":"I14","to":"I23","weight":3},{"from":"I23","to":"I14","weight":3},{"from":"I16","to":"I15","weight":2},{"from":"I24","to":"I15","weight":4},{"from":"I17","to":"I16","weight":2},{"from":"I16","to":"I25","weight":2},{"from":"I18","to":"I17","weight":4},{"from":"I26","to":"I17","weight":4},{"from":"I18","to":"I27","weight":5},{"from":"I19","to":"I20","weight":3},{"from":"I20","to":"I19","weight":3},{"from":"I28","to":"I19","weight":4},{"from":"I20","to":"I21","weight":2},{"from":"I21","to":"I20","weight":2},{"from":"I20","to":"I29","weight":3},{"from":"I21","to":"I22","weight":3},{"from":"I22","to":"I21","weight":3},{"from":"I30","to":"I21","weight":3},{"from":"I22","to":"I23","weight":5},{"from":"I23","to":"I22","weight":5},{"from":"I22","to":"I31","weight":2},{"from":"I23","to":"I24","weight":5},{"from":"I24","to":"I23","weight":5},{"from":"I23","to":"I32","weight":5},{"from":"I32","to":"I23","weight":5},{"from":"I24","to":"I25","weight":2},{"from":"I25","to":"I24","weight":2},{"from":"I33","to":"I24","weight":2},{"from":"I25","to":"I26","weight":4},{"from":"I26","to":"I25","weight":4},{"from":"I25","to":"I34","weight":3},{"from":"I26","to":"I27","weight":5},{"from":"I27","to":"I26","weight":5},{"from":"I35","to":"I26","weight":5},{"from":"I27","to":"I36","weight":3},{"from":"I28","to":"I29","weight":3},{"from":"I37","to":"I28","weight":4},{"from":"I29","to":"I30","weight":2},{"from":"I29","to":"I38","weight":4},{"from":"I30","to":"I31","weight":4},{"from":"I39","to":"I30","weight":3},{"from":"I31","to":"I32","weight":5},{"from":"I31","to":"I40","weight":3},{"from":"I32","to":"I33","weight":5},{"from":"I32","to":"I41","weight":4},{"from":"I41","to":"I32","weight":4},{"from":"I33","to":"I34","weight":3},{"from":"I42","to":"I33","weight":2},{"from":"I34","to":"I35","weight":5},{"from":"I34","to":"I43","weight":3},{"from":"I35","to":"I36","weight":5},{"from":"I44","to":"I35","weight":2},{"from":"I36","to":"I45","weight":2},{"from":"I38","to":"I37","weight":3},{"from":"I39","to":"I38","weight":2},{"from":"I40","to":"I39","weight":2},{"from":"I41","to":"I40","weight":2},{"from":"I42","to":"I41","weight":2},{"from":"I43","to":"I42","weight":3},{"from":"I44","to":"I43","weight":5},{"from":"I45","to":"I44","weight":3}],"details":{"vertices":45,"edges":88,"directed":true,"weighted":true,"acyclic":false,"weightMin":2,"weightMax":5,"negativeWeights":false,"density":0.044444444444444446,"inDegree":{"min":1,"avg":1.9555555555555555,"max":4},"outDegree":{"min":1,"avg":1.9555555555555555,"max":4},"selfLoops":0,"components":1}},"problem":"What are the three quickest drives from I23 to I18 that don't pass the same place twice, and how much slower is each one than the first?","params":{"start":"I23","goal":"I18","k":3},"result":{"kind":"routes","routes":[{"vertices":["I23","I24","I25","I26","I17","I8","I9","I18"],"cost":26},{"vertices":["I23","I14","I5","I6","I7","I8","I9","I18"],"cost":27},{"vertices":["I23","I24","I15","I6","I7","I8","I9","I18"],"cost":27}]},"answer":"The three quickest drives from I23 to I18 take 26, 27 and 27 minutes. Route 2 is 1 minute slower and shares 23% of route 1's time. Route 3 is 1 minute slower and shares 42% 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 I18 finds the exact time to it from each of the 45 vertices I23 reaches: 45 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 I23 finds the quickest route, 26 minutes, after taking 8 vertices from its queue. It is the first candidate.","ops":[{"panel":"candidates","list":[{"key":"From I23","note":"26 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: 26 minutes.","ops":[{"e":["I23","I24"],"state":"route-1"},{"e":["I24","I25"],"state":"route-1"},{"e":["I25","I26"],"state":"route-1"},{"e":["I26","I17"],"state":"route-1"},{"e":["I17","I8"],"state":"route-1"},{"e":["I8","I9"],"state":"route-1"},{"e":["I9","I18"],"state":"route-1"},{"v":"I23","state":"done"},{"v":"I24","state":"done"},{"v":"I25","state":"done"},{"v":"I26","state":"done"},{"v":"I17","state":"done"},{"v":"I8","state":"done"},{"v":"I9","state":"done"},{"v":"I18","state":"done"},{"panel":"candidates","list":[]},{"panel":"routes","list":[{"key":"Route 1","note":"26 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"0"}},{"panel":"numbers","set":{"Route 1":"26 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from I23: block I23 to I24, the road the route takes from here. An A* search from I23, at 0 minutes so far, takes 8 vertices from its queue and finds a way around: a candidate of 27 minutes.","ops":[{"v":"I23","state":"current"},{"e":["I23","I24"],"state":"blocked"},{"e":["I23","I14"],"state":"detour"},{"e":["I14","I5"],"state":"detour"},{"e":["I5","I6"],"state":"detour"},{"e":["I6","I7"],"state":"detour"},{"e":["I7","I8"],"state":"detour"},{"e":["I8","I9"],"state":"detour"},{"e":["I9","I18"],"state":"detour"},{"panel":"candidates","list":[{"key":"From I23","note":"27 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"1"}},{"panel":"numbers","set":{"Route 1":"26 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from I24: block I24 to I25, the road the route takes from here, and I23 before I24 so the detour can't loop back. An A* search from I24, at 5 minutes so far, takes 7 vertices from its queue and finds a way around: a candidate of 27 minutes.","ops":[{"v":"I23","state":"done"},{"e":["I23","I24"],"state":"route-1"},{"e":["I23","I14"],"state":"idle"},{"e":["I14","I5"],"state":"idle"},{"e":["I5","I6"],"state":"idle"},{"e":["I6","I7"],"state":"idle"},{"e":["I7","I8"],"state":"idle"},{"e":["I8","I9"],"state":"route-1"},{"e":["I9","I18"],"state":"route-1"},{"v":"I24","state":"current"},{"v":"I23","state":"blocked"},{"e":["I24","I25"],"state":"blocked"},{"e":["I24","I15"],"state":"detour"},{"e":["I15","I6"],"state":"detour"},{"e":["I6","I7"],"state":"detour"},{"e":["I7","I8"],"state":"detour"},{"e":["I8","I9"],"state":"detour"},{"e":["I9","I18"],"state":"detour"},{"panel":"candidates","list":[{"key":"From I23","note":"27 min"},{"key":"From I24","note":"27 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"2"}},{"panel":"numbers","set":{"Route 1":"26 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from I25: block I25 to I26, the road the route takes from here, and I23 and I24 before I25 so the detour can't loop back. An A* search from I25, at 7 minutes so far, takes 2 vertices from its queue and finds no way around quicker than the slowest candidate kept, 27.","ops":[{"v":"I24","state":"done"},{"v":"I23","state":"done"},{"e":["I24","I25"],"state":"route-1"},{"e":["I24","I15"],"state":"idle"},{"e":["I15","I6"],"state":"idle"},{"e":["I6","I7"],"state":"idle"},{"e":["I7","I8"],"state":"idle"},{"e":["I8","I9"],"state":"route-1"},{"e":["I9","I18"],"state":"route-1"},{"v":"I25","state":"current"},{"v":"I24","state":"blocked"},{"v":"I23","state":"blocked"},{"e":["I25","I26"],"state":"blocked"},{"panel":"candidates","list":[{"key":"From I23","note":"27 min"},{"key":"From I24","note":"27 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"2"}},{"panel":"numbers","set":{"Route 1":"26 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from I26: block I26 to I17, the road the route takes from here, and I23, I24 and I25 before I26 so the detour can't loop back. An A* search from I26, at 11 minutes so far, takes 2 vertices from its queue and finds no way around quicker than the slowest candidate kept, 27.","ops":[{"v":"I25","state":"done"},{"v":"I24","state":"done"},{"v":"I23","state":"done"},{"e":["I25","I26"],"state":"route-1"},{"v":"I26","state":"current"},{"v":"I24","state":"blocked"},{"v":"I25","state":"blocked"},{"v":"I23","state":"blocked"},{"e":["I26","I17"],"state":"blocked"},{"panel":"candidates","list":[{"key":"From I23","note":"27 min"},{"key":"From I24","note":"27 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"2"}},{"panel":"numbers","set":{"Route 1":"26 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from I17: block I17 to I8, the road the route takes from here, and the 4 vertices before I17 so the detour can't loop back. An A* search from I17, at 15 minutes so far, takes 2 vertices from its queue and finds no way around quicker than the slowest candidate kept, 27.","ops":[{"v":"I26","state":"done"},{"v":"I24","state":"done"},{"v":"I25","state":"done"},{"v":"I23","state":"done"},{"e":["I26","I17"],"state":"route-1"},{"v":"I17","state":"current"},{"v":"I24","state":"blocked"},{"v":"I25","state":"blocked"},{"v":"I26","state":"blocked"},{"v":"I23","state":"blocked"},{"e":["I17","I8"],"state":"blocked"},{"panel":"candidates","list":[{"key":"From I23","note":"27 min"},{"key":"From I24","note":"27 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"2"}},{"panel":"numbers","set":{"Route 1":"26 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from I8: block I8 to I9, the road the route takes from here, and the 5 vertices before I8 so the detour can't loop back. An A* search from I8, at 20 minutes so far, takes 1 vertex from its queue and finds no way around quicker than the slowest candidate kept, 27.","ops":[{"v":"I17","state":"done"},{"v":"I24","state":"done"},{"v":"I25","state":"done"},{"v":"I26","state":"done"},{"v":"I23","state":"done"},{"e":["I17","I8"],"state":"route-1"},{"v":"I8","state":"current"},{"v":"I24","state":"blocked"},{"v":"I25","state":"blocked"},{"v":"I26","state":"blocked"},{"v":"I17","state":"blocked"},{"v":"I23","state":"blocked"},{"e":["I8","I9"],"state":"blocked"},{"panel":"candidates","list":[{"key":"From I23","note":"27 min"},{"key":"From I24","note":"27 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"2"}},{"panel":"numbers","set":{"Route 1":"26 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from I9: block I9 to I18, the road the route takes from here, and the 6 vertices before I9 so the detour can't loop back. An A* search from I9, at 24 minutes so far, takes 1 vertex from its queue and finds no way around quicker than the slowest candidate kept, 27.","ops":[{"v":"I8","state":"done"},{"v":"I24","state":"done"},{"v":"I25","state":"done"},{"v":"I26","state":"done"},{"v":"I17","state":"done"},{"v":"I23","state":"done"},{"e":["I8","I9"],"state":"route-1"},{"v":"I9","state":"current"},{"v":"I24","state":"blocked"},{"v":"I25","state":"blocked"},{"v":"I26","state":"blocked"},{"v":"I17","state":"blocked"},{"v":"I8","state":"blocked"},{"v":"I23","state":"blocked"},{"e":["I9","I18"],"state":"blocked"},{"panel":"candidates","list":[{"key":"From I23","note":"27 min"},{"key":"From I24","note":"27 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"2"}},{"panel":"numbers","set":{"Route 1":"26 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Route 2 is the quickest candidate: 27 minutes, 1 minute slower than route 1, sharing 23% of its time.","ops":[{"v":"I9","state":"done"},{"v":"I24","state":"done"},{"v":"I25","state":"done"},{"v":"I26","state":"done"},{"v":"I17","state":"done"},{"v":"I8","state":"done"},{"v":"I23","state":"done"},{"e":["I9","I18"],"state":"route-1"},{"e":["I23","I14"],"state":"route-2"},{"e":["I14","I5"],"state":"route-2"},{"e":["I5","I6"],"state":"route-2"},{"e":["I6","I7"],"state":"route-2"},{"e":["I7","I8"],"state":"route-2"},{"v":"I23","state":"done"},{"v":"I14","state":"done"},{"v":"I5","state":"done"},{"v":"I6","state":"done"},{"v":"I7","state":"done"},{"v":"I8","state":"done"},{"v":"I9","state":"done"},{"v":"I18","state":"done"},{"panel":"candidates","list":[{"key":"From I24","note":"27 min"}]},{"panel":"routes","list":[{"key":"Route 1","note":"26 min"},{"key":"Route 2","note":"27 min"}]},{"panel":"numbers","set":{"Routes found":"2"}},{"panel":"numbers","set":{"Candidates waiting":"1"}},{"panel":"numbers","set":{"Route 1":"26 min"}},{"panel":"numbers","set":{"Route 2":"27 min, shares 23%"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from I23: block I23 to I14 and I23 to I24, the roads the routes so far take from here. An A* search from I23, at 0 minutes so far, takes 2 vertices from its queue and finds no way around quicker than the slowest candidate kept, 27.","ops":[{"v":"I23","state":"current"},{"e":["I23","I14"],"state":"blocked"},{"e":["I23","I24"],"state":"blocked"},{"panel":"candidates","list":[{"key":"From I24","note":"27 min"}]},{"panel":"numbers","set":{"Routes found":"2"}},{"panel":"numbers","set":{"Candidates waiting":"1"}},{"panel":"numbers","set":{"Route 1":"26 min"}},{"panel":"numbers","set":{"Route 2":"27 min, shares 23%"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from I14: the route up to I14 takes 3 minutes, and the quickest time on from I14 is 24, so the best detour would be 27. That's no quicker than the slowest candidate kept, 27, so skip it.","ops":[{"v":"I23","state":"done"},{"e":["I23","I14"],"state":"route-2"},{"e":["I23","I24"],"state":"route-1"},{"v":"I14","state":"current"}]},{"say":"Detour from I5: the route up to I5 takes 8 minutes, and the quickest time on from I5 is 19, so the best detour would be 27. That's no quicker than the slowest candidate kept, 27, so skip it.","ops":[{"v":"I14","state":"done"},{"v":"I5","state":"current"}]},{"say":"Detour from I6: the route up to I6 takes 13 minutes, and the quickest time on from I6 is 14, so the best detour would be 27. That's no quicker than the slowest candidate kept, 27, so skip it.","ops":[{"v":"I5","state":"done"},{"v":"I6","state":"current"}]},{"say":"Detour from I7: the route up to I7 takes 17 minutes, and the quickest time on from I7 is 10, so the best detour would be 27. That's no quicker than the slowest candidate kept, 27, so skip it.","ops":[{"v":"I6","state":"done"},{"v":"I7","state":"current"}]},{"say":"Detour from I8: the route up to I8 takes 21 minutes, and the quickest time on from I8 is 6, so the best detour would be 27. That's no quicker than the slowest candidate kept, 27, so skip it.","ops":[{"v":"I7","state":"done"},{"v":"I8","state":"current"}]},{"say":"Detour from I9: the route up to I9 takes 25 minutes, and the quickest time on from I9 is 2, so the best detour would be 27. That's no quicker than the slowest candidate kept, 27, so skip it.","ops":[{"v":"I8","state":"done"},{"v":"I9","state":"current"}]},{"say":"Route 3 is the quickest candidate: 27 minutes, 1 minute slower than route 1, sharing 42% of its time.","ops":[{"v":"I9","state":"done"},{"e":["I24","I15"],"state":"route-3"},{"e":["I15","I6"],"state":"route-3"},{"v":"I23","state":"done"},{"v":"I24","state":"done"},{"v":"I15","state":"done"},{"v":"I6","state":"done"},{"v":"I7","state":"done"},{"v":"I8","state":"done"},{"v":"I9","state":"done"},{"v":"I18","state":"done"},{"panel":"candidates","list":[]},{"panel":"routes","list":[{"key":"Route 1","note":"26 min"},{"key":"Route 2","note":"27 min"},{"key":"Route 3","note":"27 min"}]},{"panel":"numbers","set":{"Routes found":"3"}},{"panel":"numbers","set":{"Candidates waiting":"0"}},{"panel":"numbers","set":{"Route 1":"26 min"}},{"panel":"numbers","set":{"Route 2":"27 min, shares 23%"}},{"panel":"numbers","set":{"Route 3":"27 min, shares 42%"}}]},{"say":"Done. The three quickest routes take 26, 27 and 27 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, \"I23\", \"I18\", 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}"}
