{"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":"metro-region","name":"Metro region","description":"A hundred towns, T1 to T100, where T stands for town, numbered row by row from the top left with ten to a row. Two fast motorways cross at T45: one runs from T41 to T50, the other through T5, T15 and on down to T95. Local roads join neighboring towns, a few of them one way, and each edge is the travel time in minutes.","family":"road","directed":true,"weighted":true,"acyclic":false,"vertices":[{"id":"T1","x":58,"y":56},{"id":"T2","x":157,"y":56},{"id":"T3","x":257,"y":62},{"id":"T4","x":359,"y":61},{"id":"T5","x":454,"y":61},{"id":"T6","x":547,"y":50},{"id":"T7","x":653,"y":55},{"id":"T8","x":750,"y":63},{"id":"T9","x":847,"y":67},{"id":"T10","x":941,"y":64},{"id":"T11","x":55,"y":156},{"id":"T12","x":155,"y":153},{"id":"T13","x":263,"y":148},{"id":"T14","x":362,"y":149},{"id":"T15","x":452,"y":149},{"id":"T16","x":540,"y":162},{"id":"T17","x":640,"y":150},{"id":"T18","x":740,"y":149},{"id":"T19","x":835,"y":164},{"id":"T20","x":936,"y":162},{"id":"T21","x":59,"y":247},{"id":"T22","x":164,"y":250},{"id":"T23","x":252,"y":253},{"id":"T24","x":358,"y":265},{"id":"T25","x":450,"y":259},{"id":"T26","x":559,"y":262},{"id":"T27","x":639,"y":254},{"id":"T28","x":739,"y":257},{"id":"T29","x":852,"y":264},{"id":"T30","x":940,"y":254},{"id":"T31","x":69,"y":350},{"id":"T32","x":157,"y":346},{"id":"T33","x":258,"y":362},{"id":"T34","x":353,"y":356},{"id":"T35","x":453,"y":356},{"id":"T36","x":558,"y":359},{"id":"T37","x":640,"y":360},{"id":"T38","x":742,"y":352},{"id":"T39","x":848,"y":361},{"id":"T40","x":940,"y":356},{"id":"T41","x":62,"y":457},{"id":"T42","x":161,"y":455},{"id":"T43","x":254,"y":448},{"id":"T44","x":345,"y":449},{"id":"T45","x":444,"y":455},{"id":"T46","x":544,"y":449},{"id":"T47","x":652,"y":460},{"id":"T48","x":737,"y":448},{"id":"T49","x":849,"y":448},{"id":"T50","x":946,"y":449},{"id":"T51","x":58,"y":546},{"id":"T52","x":150,"y":550},{"id":"T53","x":258,"y":540},{"id":"T54","x":354,"y":548},{"id":"T55","x":445,"y":540},{"id":"T56","x":554,"y":553},{"id":"T57","x":652,"y":547},{"id":"T58","x":750,"y":552},{"id":"T59","x":842,"y":550},{"id":"T60","x":948,"y":542},{"id":"T61","x":56,"y":637},{"id":"T62","x":158,"y":648},{"id":"T63","x":259,"y":653},{"id":"T64","x":356,"y":639},{"id":"T65","x":444,"y":639},{"id":"T66","x":556,"y":652},{"id":"T67","x":653,"y":639},{"id":"T68","x":748,"y":655},{"id":"T69","x":840,"y":655},{"id":"T70","x":948,"y":649},{"id":"T71","x":63,"y":740},{"id":"T72","x":163,"y":738},{"id":"T73","x":249,"y":742},{"id":"T74","x":352,"y":752},{"id":"T75","x":450,"y":753},{"id":"T76","x":544,"y":748},{"id":"T77","x":655,"y":753},{"id":"T78","x":748,"y":736},{"id":"T79","x":840,"y":747},{"id":"T80","x":939,"y":747},{"id":"T81","x":57,"y":841},{"id":"T82","x":157,"y":844},{"id":"T83","x":249,"y":843},{"id":"T84","x":347,"y":837},{"id":"T85","x":447,"y":841},{"id":"T86","x":541,"y":847},{"id":"T87","x":637,"y":834},{"id":"T88","x":738,"y":839},{"id":"T89","x":836,"y":848},{"id":"T90","x":942,"y":833},{"id":"T91","x":54,"y":940},{"id":"T92","x":164,"y":939},{"id":"T93","x":256,"y":931},{"id":"T94","x":354,"y":946},{"id":"T95","x":446,"y":949},{"id":"T96","x":542,"y":935},{"id":"T97","x":654,"y":937},{"id":"T98","x":750,"y":948},{"id":"T99","x":848,"y":935},{"id":"T100","x":933,"y":937}],"edges":[{"from":"T1","to":"T2","weight":7},{"from":"T2","to":"T1","weight":7},{"from":"T1","to":"T11","weight":6},{"from":"T11","to":"T1","weight":6},{"from":"T2","to":"T3","weight":6},{"from":"T3","to":"T2","weight":6},{"from":"T2","to":"T12","weight":7},{"from":"T3","to":"T4","weight":5},{"from":"T4","to":"T3","weight":5},{"from":"T3","to":"T13","weight":9},{"from":"T13","to":"T3","weight":9},{"from":"T4","to":"T5","weight":7},{"from":"T5","to":"T4","weight":7},{"from":"T4","to":"T14","weight":8},{"from":"T14","to":"T4","weight":8},{"from":"T5","to":"T6","weight":4},{"from":"T6","to":"T5","weight":4},{"from":"T5","to":"T15","weight":2},{"from":"T15","to":"T5","weight":2},{"from":"T6","to":"T7","weight":4},{"from":"T7","to":"T6","weight":4},{"from":"T6","to":"T16","weight":5},{"from":"T16","to":"T6","weight":5},{"from":"T7","to":"T8","weight":4},{"from":"T8","to":"T7","weight":4},{"from":"T17","to":"T7","weight":8},{"from":"T8","to":"T9","weight":5},{"from":"T9","to":"T8","weight":5},{"from":"T8","to":"T18","weight":7},{"from":"T18","to":"T8","weight":7},{"from":"T9","to":"T10","weight":7},{"from":"T10","to":"T9","weight":7},{"from":"T10","to":"T20","weight":6},{"from":"T20","to":"T10","weight":6},{"from":"T11","to":"T12","weight":9},{"from":"T12","to":"T11","weight":9},{"from":"T21","to":"T11","weight":6},{"from":"T11","to":"T22","weight":10},{"from":"T22","to":"T11","weight":10},{"from":"T12","to":"T13","weight":4},{"from":"T13","to":"T12","weight":4},{"from":"T12","to":"T22","weight":4},{"from":"T22","to":"T12","weight":4},{"from":"T13","to":"T22","weight":7},{"from":"T22","to":"T13","weight":7},{"from":"T13","to":"T14","weight":5},{"from":"T14","to":"T15","weight":6},{"from":"T15","to":"T14","weight":6},{"from":"T14","to":"T24","weight":9},{"from":"T24","to":"T14","weight":9},{"from":"T15","to":"T16","weight":4},{"from":"T16","to":"T15","weight":4},{"from":"T15","to":"T25","weight":2},{"from":"T25","to":"T15","weight":2},{"from":"T15","to":"T26","weight":9},{"from":"T26","to":"T15","weight":9},{"from":"T16","to":"T17","weight":9},{"from":"T17","to":"T16","weight":9},{"from":"T16","to":"T26","weight":8},{"from":"T26","to":"T16","weight":8},{"from":"T17","to":"T26","weight":7},{"from":"T26","to":"T17","weight":7},{"from":"T17","to":"T18","weight":9},{"from":"T18","to":"T17","weight":9},{"from":"T17","to":"T27","weight":9},{"from":"T27","to":"T17","weight":9},{"from":"T17","to":"T28","weight":11},{"from":"T28","to":"T17","weight":11},{"from":"T18","to":"T19","weight":7},{"from":"T19","to":"T18","weight":7},{"from":"T18","to":"T28","weight":6},{"from":"T28","to":"T18","weight":6},{"from":"T19","to":"T20","weight":8},{"from":"T20","to":"T19","weight":8},{"from":"T29","to":"T19","weight":9},{"from":"T19","to":"T30","weight":10},{"from":"T30","to":"T19","weight":10},{"from":"T20","to":"T30","weight":9},{"from":"T30","to":"T20","weight":9},{"from":"T21","to":"T22","weight":8},{"from":"T22","to":"T21","weight":8},{"from":"T21","to":"T31","weight":7},{"from":"T31","to":"T21","weight":7},{"from":"T22","to":"T32","weight":6},{"from":"T32","to":"T22","weight":6},{"from":"T23","to":"T24","weight":5},{"from":"T24","to":"T23","weight":5},{"from":"T23","to":"T33","weight":8},{"from":"T33","to":"T23","weight":8},{"from":"T24","to":"T25","weight":9},{"from":"T25","to":"T24","weight":9},{"from":"T24","to":"T34","weight":6},{"from":"T25","to":"T26","weight":6},{"from":"T26","to":"T25","weight":6},{"from":"T25","to":"T35","weight":2},{"from":"T35","to":"T25","weight":2},{"from":"T27","to":"T36","weight":10},{"from":"T36","to":"T27","weight":10},{"from":"T27","to":"T37","weight":6},{"from":"T37","to":"T27","weight":6},{"from":"T28","to":"T37","weight":10},{"from":"T37","to":"T28","weight":10},{"from":"T28","to":"T29","weight":5},{"from":"T29","to":"T28","weight":5},{"from":"T38","to":"T28","weight":8},{"from":"T30","to":"T29","weight":6},{"from":"T29","to":"T39","weight":9},{"from":"T39","to":"T29","weight":9},{"from":"T30","to":"T40","weight":8},{"from":"T40","to":"T30","weight":8},{"from":"T31","to":"T42","weight":9},{"from":"T42","to":"T31","weight":9},{"from":"T32","to":"T33","weight":6},{"from":"T33","to":"T32","weight":6},{"from":"T32","to":"T42","weight":4},{"from":"T42","to":"T32","weight":4},{"from":"T33","to":"T34","weight":4},{"from":"T34","to":"T33","weight":4},{"from":"T33","to":"T43","weight":9},{"from":"T43","to":"T33","weight":9},{"from":"T34","to":"T35","weight":5},{"from":"T35","to":"T34","weight":5},{"from":"T34","to":"T44","weight":4},{"from":"T44","to":"T34","weight":4},{"from":"T35","to":"T36","weight":7},{"from":"T36","to":"T35","weight":7},{"from":"T35","to":"T45","weight":2},{"from":"T45","to":"T35","weight":2},{"from":"T35","to":"T46","weight":7},{"from":"T46","to":"T35","weight":7},{"from":"T37","to":"T36","weight":4},{"from":"T46","to":"T36","weight":9},{"from":"T37","to":"T38","weight":8},{"from":"T38","to":"T37","weight":8},{"from":"T37","to":"T47","weight":8},{"from":"T47","to":"T37","weight":8},{"from":"T38","to":"T39","weight":6},{"from":"T39","to":"T38","weight":6},{"from":"T38","to":"T48","weight":4},{"from":"T48","to":"T38","weight":4},{"from":"T39","to":"T40","weight":7},{"from":"T40","to":"T39","weight":7},{"from":"T39","to":"T49","weight":5},{"from":"T49","to":"T39","weight":5},{"from":"T40","to":"T50","weight":4},{"from":"T50","to":"T40","weight":4},{"from":"T41","to":"T42","weight":2},{"from":"T42","to":"T41","weight":2},{"from":"T41","to":"T51","weight":4},{"from":"T42","to":"T43","weight":3},{"from":"T43","to":"T42","weight":3},{"from":"T42","to":"T52","weight":7},{"from":"T52","to":"T42","weight":7},{"from":"T43","to":"T44","weight":2},{"from":"T44","to":"T43","weight":2},{"from":"T43","to":"T53","weight":8},{"from":"T53","to":"T43","weight":8},{"from":"T44","to":"T53","weight":11},{"from":"T53","to":"T44","weight":11},{"from":"T44","to":"T45","weight":3},{"from":"T45","to":"T44","weight":3},{"from":"T44","to":"T54","weight":7},{"from":"T54","to":"T44","weight":7},{"from":"T45","to":"T46","weight":3},{"from":"T46","to":"T45","weight":3},{"from":"T45","to":"T55","weight":2},{"from":"T55","to":"T45","weight":2},{"from":"T46","to":"T47","weight":3},{"from":"T47","to":"T46","weight":3},{"from":"T56","to":"T46","weight":7},{"from":"T47","to":"T48","weight":3},{"from":"T48","to":"T47","weight":3},{"from":"T47","to":"T57","weight":5},{"from":"T57","to":"T47","weight":5},{"from":"T48","to":"T49","weight":2},{"from":"T49","to":"T48","weight":2},{"from":"T48","to":"T58","weight":7},{"from":"T58","to":"T48","weight":7},{"from":"T49","to":"T50","weight":2},{"from":"T50","to":"T49","weight":2},{"from":"T49","to":"T59","weight":4},{"from":"T50","to":"T60","weight":6},{"from":"T60","to":"T50","weight":6},{"from":"T51","to":"T52","weight":9},{"from":"T52","to":"T51","weight":9},{"from":"T51","to":"T61","weight":8},{"from":"T61","to":"T51","weight":8},{"from":"T52","to":"T61","weight":8},{"from":"T61","to":"T52","weight":8},{"from":"T52","to":"T53","weight":6},{"from":"T53","to":"T52","weight":6},{"from":"T52","to":"T62","weight":7},{"from":"T62","to":"T52","weight":7},{"from":"T53","to":"T54","weight":7},{"from":"T54","to":"T53","weight":7},{"from":"T54","to":"T55","weight":6},{"from":"T55","to":"T54","weight":6},{"from":"T54","to":"T64","weight":4},{"from":"T64","to":"T54","weight":4},{"from":"T55","to":"T56","weight":6},{"from":"T55","to":"T65","weight":3},{"from":"T65","to":"T55","weight":3},{"from":"T55","to":"T66","weight":10},{"from":"T66","to":"T55","weight":10},{"from":"T56","to":"T57","weight":7},{"from":"T57","to":"T56","weight":7},{"from":"T57","to":"T58","weight":6},{"from":"T58","to":"T57","weight":6},{"from":"T67","to":"T57","weight":6},{"from":"T57","to":"T68","weight":10},{"from":"T68","to":"T57","weight":10},{"from":"T58","to":"T59","weight":8},{"from":"T59","to":"T58","weight":8},{"from":"T58","to":"T68","weight":4},{"from":"T68","to":"T58","weight":4},{"from":"T59","to":"T60","weight":8},{"from":"T60","to":"T59","weight":8},{"from":"T59","to":"T69","weight":9},{"from":"T69","to":"T59","weight":9},{"from":"T60","to":"T70","weight":7},{"from":"T70","to":"T60","weight":7},{"from":"T61","to":"T62","weight":4},{"from":"T62","to":"T61","weight":4},{"from":"T61","to":"T71","weight":8},{"from":"T71","to":"T61","weight":8},{"from":"T62","to":"T63","weight":9},{"from":"T62","to":"T72","weight":4},{"from":"T72","to":"T62","weight":4},{"from":"T63","to":"T64","weight":8},{"from":"T64","to":"T63","weight":8},{"from":"T63","to":"T73","weight":4},{"from":"T73","to":"T63","weight":4},{"from":"T63","to":"T74","weight":10},{"from":"T74","to":"T63","weight":10},{"from":"T64","to":"T65","weight":7},{"from":"T65","to":"T64","weight":7},{"from":"T64","to":"T74","weight":4},{"from":"T74","to":"T64","weight":4},{"from":"T65","to":"T66","weight":4},{"from":"T66","to":"T65","weight":4},{"from":"T65","to":"T75","weight":2},{"from":"T75","to":"T65","weight":2},{"from":"T66","to":"T67","weight":8},{"from":"T67","to":"T66","weight":8},{"from":"T66","to":"T76","weight":5},{"from":"T76","to":"T66","weight":5},{"from":"T66","to":"T77","weight":11},{"from":"T77","to":"T66","weight":11},{"from":"T68","to":"T67","weight":8},{"from":"T67","to":"T77","weight":8},{"from":"T77","to":"T67","weight":8},{"from":"T68","to":"T78","weight":7},{"from":"T78","to":"T68","weight":7},{"from":"T69","to":"T79","weight":5},{"from":"T79","to":"T69","weight":5},{"from":"T71","to":"T72","weight":9},{"from":"T72","to":"T71","weight":9},{"from":"T71","to":"T81","weight":5},{"from":"T81","to":"T71","weight":5},{"from":"T72","to":"T82","weight":8},{"from":"T82","to":"T72","weight":8},{"from":"T73","to":"T74","weight":7},{"from":"T74","to":"T73","weight":7},{"from":"T73","to":"T83","weight":7},{"from":"T83","to":"T73","weight":7},{"from":"T75","to":"T74","weight":6},{"from":"T75","to":"T76","weight":8},{"from":"T76","to":"T75","weight":8},{"from":"T75","to":"T85","weight":2},{"from":"T85","to":"T75","weight":2},{"from":"T76","to":"T77","weight":4},{"from":"T77","to":"T76","weight":4},{"from":"T76","to":"T86","weight":6},{"from":"T86","to":"T76","weight":6},{"from":"T77","to":"T78","weight":7},{"from":"T78","to":"T77","weight":7},{"from":"T77","to":"T87","weight":4},{"from":"T87","to":"T77","weight":4},{"from":"T78","to":"T89","weight":8},{"from":"T89","to":"T78","weight":8},{"from":"T79","to":"T89","weight":6},{"from":"T89","to":"T79","weight":6},{"from":"T80","to":"T90","weight":4},{"from":"T90","to":"T80","weight":4},{"from":"T81","to":"T82","weight":4},{"from":"T82","to":"T81","weight":4},{"from":"T81","to":"T91","weight":4},{"from":"T91","to":"T81","weight":4},{"from":"T82","to":"T83","weight":8},{"from":"T83","to":"T82","weight":8},{"from":"T82","to":"T92","weight":4},{"from":"T92","to":"T82","weight":4},{"from":"T82","to":"T93","weight":10},{"from":"T93","to":"T82","weight":10},{"from":"T83","to":"T84","weight":5},{"from":"T84","to":"T83","weight":5},{"from":"T83","to":"T93","weight":9},{"from":"T93","to":"T83","weight":9},{"from":"T84","to":"T93","weight":11},{"from":"T93","to":"T84","weight":11},{"from":"T84","to":"T85","weight":6},{"from":"T85","to":"T84","weight":6},{"from":"T84","to":"T94","weight":5},{"from":"T94","to":"T84","weight":5},{"from":"T85","to":"T86","weight":5},{"from":"T86","to":"T85","weight":5},{"from":"T85","to":"T95","weight":3},{"from":"T95","to":"T85","weight":3},{"from":"T86","to":"T95","weight":10},{"from":"T95","to":"T86","weight":10},{"from":"T86","to":"T87","weight":4},{"from":"T87","to":"T86","weight":4},{"from":"T86","to":"T96","weight":7},{"from":"T96","to":"T86","weight":7},{"from":"T87","to":"T96","weight":10},{"from":"T96","to":"T87","weight":10},{"from":"T87","to":"T88","weight":6},{"from":"T88","to":"T87","weight":6},{"from":"T87","to":"T97","weight":5},{"from":"T97","to":"T87","weight":5},{"from":"T88","to":"T89","weight":5},{"from":"T89","to":"T88","weight":5},{"from":"T88","to":"T98","weight":9},{"from":"T98","to":"T88","weight":9},{"from":"T89","to":"T90","weight":4},{"from":"T90","to":"T89","weight":4},{"from":"T89","to":"T99","weight":7},{"from":"T99","to":"T89","weight":7},{"from":"T90","to":"T100","weight":4},{"from":"T100","to":"T90","weight":4},{"from":"T91","to":"T92","weight":4},{"from":"T92","to":"T91","weight":4},{"from":"T92","to":"T93","weight":7},{"from":"T93","to":"T92","weight":7},{"from":"T94","to":"T95","weight":4},{"from":"T95","to":"T94","weight":4},{"from":"T95","to":"T96","weight":4},{"from":"T96","to":"T95","weight":4},{"from":"T96","to":"T97","weight":7},{"from":"T97","to":"T96","weight":7},{"from":"T97","to":"T98","weight":6},{"from":"T98","to":"T97","weight":6},{"from":"T98","to":"T99","weight":7},{"from":"T99","to":"T98","weight":7},{"from":"T99","to":"T100","weight":6},{"from":"T100","to":"T99","weight":6}],"details":{"vertices":100,"edges":346,"directed":true,"weighted":true,"acyclic":false,"weightMin":2,"weightMax":11,"negativeWeights":false,"density":0.03494949494949495,"inDegree":{"min":1,"avg":3.46,"max":5},"outDegree":{"min":1,"avg":3.46,"max":6},"selfLoops":0,"components":1}},"problem":"What are the three quickest drives from T45 to T100 that don't pass the same place twice, and how much slower is each one than the first?","params":{"start":"T45","goal":"T100","k":3},"result":{"kind":"routes","routes":[{"vertices":["T45","T55","T65","T75","T85","T86","T87","T88","T89","T90","T100"],"cost":37},{"vertices":["T45","T55","T65","T66","T76","T77","T78","T89","T90","T100"],"cost":41},{"vertices":["T45","T55","T65","T66","T76","T77","T87","T88","T89","T90","T100"],"cost":41}]},"answer":"The three quickest drives from T45 to T100 take 37, 41 and 41 minutes. Route 2 is 4 minutes slower and shares 35% of route 1's time. Route 3 is 4 minutes slower and shares 65% 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 T100 finds the exact time to it from each of the 100 vertices T45 reaches: 100 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 T45 finds the quickest route, 37 minutes, after taking 11 vertices from its queue. It is the first candidate.","ops":[{"panel":"candidates","list":[{"key":"From T45","note":"37 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: 37 minutes.","ops":[{"e":["T45","T55"],"state":"route-1"},{"e":["T55","T65"],"state":"route-1"},{"e":["T65","T75"],"state":"route-1"},{"e":["T75","T85"],"state":"route-1"},{"e":["T85","T86"],"state":"route-1"},{"e":["T86","T87"],"state":"route-1"},{"e":["T87","T88"],"state":"route-1"},{"e":["T88","T89"],"state":"route-1"},{"e":["T89","T90"],"state":"route-1"},{"e":["T90","T100"],"state":"route-1"},{"v":"T45","state":"done"},{"v":"T55","state":"done"},{"v":"T65","state":"done"},{"v":"T75","state":"done"},{"v":"T85","state":"done"},{"v":"T86","state":"done"},{"v":"T87","state":"done"},{"v":"T88","state":"done"},{"v":"T89","state":"done"},{"v":"T90","state":"done"},{"v":"T100","state":"done"},{"panel":"candidates","list":[]},{"panel":"routes","list":[{"key":"Route 1","note":"37 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"0"}},{"panel":"numbers","set":{"Route 1":"37 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from T45: block T45 to T55, the road the route takes from here. An A* search from T45, at 0 minutes so far, takes 12 vertices from its queue and finds a way around: a candidate of 43 minutes.","ops":[{"v":"T45","state":"current"},{"e":["T45","T55"],"state":"blocked"},{"e":["T45","T46"],"state":"detour"},{"e":["T46","T47"],"state":"detour"},{"e":["T47","T48"],"state":"detour"},{"e":["T48","T58"],"state":"detour"},{"e":["T58","T68"],"state":"detour"},{"e":["T68","T78"],"state":"detour"},{"e":["T78","T89"],"state":"detour"},{"e":["T89","T90"],"state":"detour"},{"e":["T90","T100"],"state":"detour"},{"panel":"candidates","list":[{"key":"From T45","note":"43 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"1"}},{"panel":"numbers","set":{"Route 1":"37 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from T55: block T55 to T65, the road the route takes from here, and T45 before T55 so the detour can't loop back. An A* search from T55, at 2 minutes so far, takes 8 vertices from its queue and finds a way around: a candidate of 44 minutes.","ops":[{"v":"T45","state":"done"},{"e":["T45","T55"],"state":"route-1"},{"e":["T45","T46"],"state":"idle"},{"e":["T46","T47"],"state":"idle"},{"e":["T47","T48"],"state":"idle"},{"e":["T48","T58"],"state":"idle"},{"e":["T58","T68"],"state":"idle"},{"e":["T68","T78"],"state":"idle"},{"e":["T78","T89"],"state":"idle"},{"e":["T89","T90"],"state":"route-1"},{"e":["T90","T100"],"state":"route-1"},{"v":"T55","state":"current"},{"v":"T45","state":"blocked"},{"e":["T55","T65"],"state":"blocked"},{"e":["T55","T66"],"state":"detour"},{"e":["T66","T76"],"state":"detour"},{"e":["T76","T77"],"state":"detour"},{"e":["T77","T78"],"state":"detour"},{"e":["T78","T89"],"state":"detour"},{"e":["T89","T90"],"state":"detour"},{"e":["T90","T100"],"state":"detour"},{"panel":"candidates","list":[{"key":"From T45","note":"43 min"},{"key":"From T55","note":"44 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"2"}},{"panel":"numbers","set":{"Route 1":"37 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from T65: block T65 to T75, the road the route takes from here, and T45 and T55 before T65 so the detour can't loop back. An A* search from T65, at 5 minutes so far, takes 8 vertices from its queue and finds a way around: a candidate of 41 minutes. Only 2 candidates can still be used, so drop the slowest, 44 minutes.","ops":[{"v":"T55","state":"done"},{"v":"T45","state":"done"},{"e":["T55","T65"],"state":"route-1"},{"e":["T55","T66"],"state":"idle"},{"e":["T66","T76"],"state":"idle"},{"e":["T76","T77"],"state":"idle"},{"e":["T77","T78"],"state":"idle"},{"e":["T78","T89"],"state":"idle"},{"e":["T89","T90"],"state":"route-1"},{"e":["T90","T100"],"state":"route-1"},{"v":"T65","state":"current"},{"v":"T55","state":"blocked"},{"v":"T45","state":"blocked"},{"e":["T65","T75"],"state":"blocked"},{"e":["T65","T66"],"state":"detour"},{"e":["T66","T76"],"state":"detour"},{"e":["T76","T77"],"state":"detour"},{"e":["T77","T78"],"state":"detour"},{"e":["T78","T89"],"state":"detour"},{"e":["T89","T90"],"state":"detour"},{"e":["T90","T100"],"state":"detour"},{"panel":"candidates","list":[{"key":"From T65","note":"41 min"},{"key":"From T45","note":"43 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"2"}},{"panel":"numbers","set":{"Route 1":"37 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from T75: block T75 to T85, the road the route takes from here, and T45, T55 and T65 before T75 so the detour can't loop back. An A* search from T75, at 7 minutes so far, takes 7 vertices from its queue and finds a way around: a candidate of 42 minutes. Only 2 candidates can still be used, so drop the slowest, 43 minutes.","ops":[{"v":"T65","state":"done"},{"v":"T55","state":"done"},{"v":"T45","state":"done"},{"e":["T65","T75"],"state":"route-1"},{"e":["T65","T66"],"state":"idle"},{"e":["T66","T76"],"state":"idle"},{"e":["T76","T77"],"state":"idle"},{"e":["T77","T78"],"state":"idle"},{"e":["T78","T89"],"state":"idle"},{"e":["T89","T90"],"state":"route-1"},{"e":["T90","T100"],"state":"route-1"},{"v":"T75","state":"current"},{"v":"T55","state":"blocked"},{"v":"T65","state":"blocked"},{"v":"T45","state":"blocked"},{"e":["T75","T85"],"state":"blocked"},{"e":["T75","T76"],"state":"detour"},{"e":["T76","T77"],"state":"detour"},{"e":["T77","T78"],"state":"detour"},{"e":["T78","T89"],"state":"detour"},{"e":["T89","T90"],"state":"detour"},{"e":["T90","T100"],"state":"detour"},{"panel":"candidates","list":[{"key":"From T65","note":"41 min"},{"key":"From T75","note":"42 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"2"}},{"panel":"numbers","set":{"Route 1":"37 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from T85: block T85 to T86, the road the route takes from here, and the 4 vertices before T85 so the detour can't loop back. An A* search from T85, at 9 minutes so far, takes 2 vertices from its queue and finds no way around quicker than the slowest candidate kept, 42.","ops":[{"v":"T75","state":"done"},{"v":"T55","state":"done"},{"v":"T65","state":"done"},{"v":"T45","state":"done"},{"e":["T75","T85"],"state":"route-1"},{"e":["T75","T76"],"state":"idle"},{"e":["T76","T77"],"state":"idle"},{"e":["T77","T78"],"state":"idle"},{"e":["T78","T89"],"state":"idle"},{"e":["T89","T90"],"state":"route-1"},{"e":["T90","T100"],"state":"route-1"},{"v":"T85","state":"current"},{"v":"T55","state":"blocked"},{"v":"T65","state":"blocked"},{"v":"T75","state":"blocked"},{"v":"T45","state":"blocked"},{"e":["T85","T86"],"state":"blocked"},{"panel":"candidates","list":[{"key":"From T65","note":"41 min"},{"key":"From T75","note":"42 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"2"}},{"panel":"numbers","set":{"Route 1":"37 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from T86: block T86 to T87, the road the route takes from here, and the 5 vertices before T86 so the detour can't loop back. An A* search from T86, at 14 minutes so far, takes 2 vertices from its queue and finds no way around quicker than the slowest candidate kept, 42.","ops":[{"v":"T85","state":"done"},{"v":"T55","state":"done"},{"v":"T65","state":"done"},{"v":"T75","state":"done"},{"v":"T45","state":"done"},{"e":["T85","T86"],"state":"route-1"},{"v":"T86","state":"current"},{"v":"T55","state":"blocked"},{"v":"T65","state":"blocked"},{"v":"T75","state":"blocked"},{"v":"T85","state":"blocked"},{"v":"T45","state":"blocked"},{"e":["T86","T87"],"state":"blocked"},{"panel":"candidates","list":[{"key":"From T65","note":"41 min"},{"key":"From T75","note":"42 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"2"}},{"panel":"numbers","set":{"Route 1":"37 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from T87: block T87 to T88, the road the route takes from here, and the 6 vertices before T87 so the detour can't loop back. An A* search from T87, at 18 minutes so far, takes 2 vertices from its queue and finds no way around quicker than the slowest candidate kept, 42.","ops":[{"v":"T86","state":"done"},{"v":"T55","state":"done"},{"v":"T65","state":"done"},{"v":"T75","state":"done"},{"v":"T85","state":"done"},{"v":"T45","state":"done"},{"e":["T86","T87"],"state":"route-1"},{"v":"T87","state":"current"},{"v":"T55","state":"blocked"},{"v":"T65","state":"blocked"},{"v":"T75","state":"blocked"},{"v":"T85","state":"blocked"},{"v":"T86","state":"blocked"},{"v":"T45","state":"blocked"},{"e":["T87","T88"],"state":"blocked"},{"panel":"candidates","list":[{"key":"From T65","note":"41 min"},{"key":"From T75","note":"42 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"2"}},{"panel":"numbers","set":{"Route 1":"37 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from T88: block T88 to T89, the road the route takes from here, and the 7 vertices before T88 so the detour can't loop back. An A* search from T88, at 24 minutes so far, takes 2 vertices from its queue and finds no way around quicker than the slowest candidate kept, 42.","ops":[{"v":"T87","state":"done"},{"v":"T55","state":"done"},{"v":"T65","state":"done"},{"v":"T75","state":"done"},{"v":"T85","state":"done"},{"v":"T86","state":"done"},{"v":"T45","state":"done"},{"e":["T87","T88"],"state":"route-1"},{"v":"T88","state":"current"},{"v":"T55","state":"blocked"},{"v":"T65","state":"blocked"},{"v":"T75","state":"blocked"},{"v":"T85","state":"blocked"},{"v":"T86","state":"blocked"},{"v":"T87","state":"blocked"},{"v":"T45","state":"blocked"},{"e":["T88","T89"],"state":"blocked"},{"panel":"candidates","list":[{"key":"From T65","note":"41 min"},{"key":"From T75","note":"42 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"2"}},{"panel":"numbers","set":{"Route 1":"37 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from T89: block T89 to T90, the road the route takes from here, and the 8 vertices before T89 so the detour can't loop back. An A* search from T89, at 29 minutes so far, takes 2 vertices from its queue and finds no way around quicker than the slowest candidate kept, 42.","ops":[{"v":"T88","state":"done"},{"v":"T55","state":"done"},{"v":"T65","state":"done"},{"v":"T75","state":"done"},{"v":"T85","state":"done"},{"v":"T86","state":"done"},{"v":"T87","state":"done"},{"v":"T45","state":"done"},{"e":["T88","T89"],"state":"route-1"},{"v":"T89","state":"current"},{"v":"T55","state":"blocked"},{"v":"T65","state":"blocked"},{"v":"T75","state":"blocked"},{"v":"T85","state":"blocked"},{"v":"T86","state":"blocked"},{"v":"T87","state":"blocked"},{"v":"T88","state":"blocked"},{"v":"T45","state":"blocked"},{"e":["T89","T90"],"state":"blocked"},{"panel":"candidates","list":[{"key":"From T65","note":"41 min"},{"key":"From T75","note":"42 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"2"}},{"panel":"numbers","set":{"Route 1":"37 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from T90: block T90 to T100, the road the route takes from here, and the 9 vertices before T90 so the detour can't loop back. An A* search from T90, at 33 minutes so far, takes 2 vertices from its queue and finds no way around quicker than the slowest candidate kept, 42.","ops":[{"v":"T89","state":"done"},{"v":"T55","state":"done"},{"v":"T65","state":"done"},{"v":"T75","state":"done"},{"v":"T85","state":"done"},{"v":"T86","state":"done"},{"v":"T87","state":"done"},{"v":"T88","state":"done"},{"v":"T45","state":"done"},{"e":["T89","T90"],"state":"route-1"},{"v":"T90","state":"current"},{"v":"T55","state":"blocked"},{"v":"T65","state":"blocked"},{"v":"T75","state":"blocked"},{"v":"T85","state":"blocked"},{"v":"T86","state":"blocked"},{"v":"T87","state":"blocked"},{"v":"T88","state":"blocked"},{"v":"T89","state":"blocked"},{"v":"T45","state":"blocked"},{"e":["T90","T100"],"state":"blocked"},{"panel":"candidates","list":[{"key":"From T65","note":"41 min"},{"key":"From T75","note":"42 min"}]},{"panel":"numbers","set":{"Routes found":"1"}},{"panel":"numbers","set":{"Candidates waiting":"2"}},{"panel":"numbers","set":{"Route 1":"37 min"}},{"panel":"numbers","set":{"Route 2":"–"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Route 2 is the quickest candidate: 41 minutes, 4 minutes slower than route 1, sharing 35% of its time.","ops":[{"v":"T90","state":"done"},{"v":"T55","state":"done"},{"v":"T65","state":"done"},{"v":"T75","state":"done"},{"v":"T85","state":"done"},{"v":"T86","state":"done"},{"v":"T87","state":"done"},{"v":"T88","state":"done"},{"v":"T89","state":"done"},{"v":"T45","state":"done"},{"e":["T90","T100"],"state":"route-1"},{"e":["T65","T66"],"state":"route-2"},{"e":["T66","T76"],"state":"route-2"},{"e":["T76","T77"],"state":"route-2"},{"e":["T77","T78"],"state":"route-2"},{"e":["T78","T89"],"state":"route-2"},{"v":"T45","state":"done"},{"v":"T55","state":"done"},{"v":"T65","state":"done"},{"v":"T66","state":"done"},{"v":"T76","state":"done"},{"v":"T77","state":"done"},{"v":"T78","state":"done"},{"v":"T89","state":"done"},{"v":"T90","state":"done"},{"v":"T100","state":"done"},{"panel":"candidates","list":[{"key":"From T75","note":"42 min"}]},{"panel":"routes","list":[{"key":"Route 1","note":"37 min"},{"key":"Route 2","note":"41 min"}]},{"panel":"numbers","set":{"Routes found":"2"}},{"panel":"numbers","set":{"Candidates waiting":"1"}},{"panel":"numbers","set":{"Route 1":"37 min"}},{"panel":"numbers","set":{"Route 2":"41 min, shares 35%"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Route 2 left the route it came from at T65, so its detours start there. The vertices before it were searched for the earlier route."},{"say":"Detour from T65: block T65 to T66 and T65 to T75, the roads the routes so far take from here, and T45 and T55 before T65 so the detour can't loop back. An A* search from T65, at 5 minutes so far, takes 2 vertices from its queue and finds no way around quicker than the slowest candidate kept, 42.","ops":[{"v":"T65","state":"current"},{"v":"T55","state":"blocked"},{"v":"T45","state":"blocked"},{"e":["T65","T66"],"state":"blocked"},{"e":["T65","T75"],"state":"blocked"},{"panel":"candidates","list":[{"key":"From T75","note":"42 min"}]},{"panel":"numbers","set":{"Routes found":"2"}},{"panel":"numbers","set":{"Candidates waiting":"1"}},{"panel":"numbers","set":{"Route 1":"37 min"}},{"panel":"numbers","set":{"Route 2":"41 min, shares 35%"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from T66: block T66 to T76, the road the route takes from here, and T45, T55 and T65 before T66 so the detour can't loop back. An A* search from T66, at 9 minutes so far, takes 2 vertices from its queue and finds no way around quicker than the slowest candidate kept, 42.","ops":[{"v":"T65","state":"done"},{"v":"T55","state":"done"},{"v":"T45","state":"done"},{"e":["T65","T66"],"state":"route-2"},{"e":["T65","T75"],"state":"route-1"},{"v":"T66","state":"current"},{"v":"T55","state":"blocked"},{"v":"T65","state":"blocked"},{"v":"T45","state":"blocked"},{"e":["T66","T76"],"state":"blocked"},{"panel":"candidates","list":[{"key":"From T75","note":"42 min"}]},{"panel":"numbers","set":{"Routes found":"2"}},{"panel":"numbers","set":{"Candidates waiting":"1"}},{"panel":"numbers","set":{"Route 1":"37 min"}},{"panel":"numbers","set":{"Route 2":"41 min, shares 35%"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from T76: block T76 to T77, the road the route takes from here, and the 4 vertices before T76 so the detour can't loop back. An A* search from T76, at 14 minutes so far, takes 2 vertices from its queue and finds no way around quicker than the slowest candidate kept, 42.","ops":[{"v":"T66","state":"done"},{"v":"T55","state":"done"},{"v":"T65","state":"done"},{"v":"T45","state":"done"},{"e":["T66","T76"],"state":"route-2"},{"v":"T76","state":"current"},{"v":"T55","state":"blocked"},{"v":"T65","state":"blocked"},{"v":"T66","state":"blocked"},{"v":"T45","state":"blocked"},{"e":["T76","T77"],"state":"blocked"},{"panel":"candidates","list":[{"key":"From T75","note":"42 min"}]},{"panel":"numbers","set":{"Routes found":"2"}},{"panel":"numbers","set":{"Candidates waiting":"1"}},{"panel":"numbers","set":{"Route 1":"37 min"}},{"panel":"numbers","set":{"Route 2":"41 min, shares 35%"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from T77: block T77 to T78, the road the route takes from here, and the 5 vertices before T77 so the detour can't loop back. An A* search from T77, at 18 minutes so far, takes 6 vertices from its queue and finds a way around: a candidate of 41 minutes. Only 1 candidate can still be used, so drop the slowest, 42 minutes.","ops":[{"v":"T76","state":"done"},{"v":"T55","state":"done"},{"v":"T65","state":"done"},{"v":"T66","state":"done"},{"v":"T45","state":"done"},{"e":["T76","T77"],"state":"route-2"},{"v":"T77","state":"current"},{"v":"T55","state":"blocked"},{"v":"T65","state":"blocked"},{"v":"T66","state":"blocked"},{"v":"T76","state":"blocked"},{"v":"T45","state":"blocked"},{"e":["T77","T78"],"state":"blocked"},{"e":["T77","T87"],"state":"detour"},{"e":["T87","T88"],"state":"detour"},{"e":["T88","T89"],"state":"detour"},{"e":["T89","T90"],"state":"detour"},{"e":["T90","T100"],"state":"detour"},{"panel":"candidates","list":[{"key":"From T77","note":"41 min"}]},{"panel":"numbers","set":{"Routes found":"2"}},{"panel":"numbers","set":{"Candidates waiting":"1"}},{"panel":"numbers","set":{"Route 1":"37 min"}},{"panel":"numbers","set":{"Route 2":"41 min, shares 35%"}},{"panel":"numbers","set":{"Route 3":"–"}}]},{"say":"Detour from T78: the route up to T78 takes 25 minutes, and the quickest time on from T78 is 16, so the best detour would be 41. That's no quicker than the slowest candidate kept, 41, so skip it.","ops":[{"v":"T77","state":"done"},{"v":"T55","state":"done"},{"v":"T65","state":"done"},{"v":"T66","state":"done"},{"v":"T76","state":"done"},{"v":"T45","state":"done"},{"e":["T77","T78"],"state":"route-2"},{"e":["T77","T87"],"state":"idle"},{"e":["T87","T88"],"state":"route-1"},{"e":["T88","T89"],"state":"route-1"},{"e":["T89","T90"],"state":"route-1"},{"e":["T90","T100"],"state":"route-1"},{"v":"T78","state":"current"}]},{"say":"Detour from T89: the route up to T89 takes 33 minutes, and the quickest time on from T89 is 8, so the best detour would be 41. That's no quicker than the slowest candidate kept, 41, so skip it.","ops":[{"v":"T78","state":"done"},{"v":"T89","state":"current"}]},{"say":"Detour from T90: the route up to T90 takes 37 minutes, and the quickest time on from T90 is 4, so the best detour would be 41. That's no quicker than the slowest candidate kept, 41, so skip it.","ops":[{"v":"T89","state":"done"},{"v":"T90","state":"current"}]},{"say":"Route 3 is the quickest candidate: 41 minutes, 4 minutes slower than route 1, sharing 65% of its time.","ops":[{"v":"T90","state":"done"},{"e":["T77","T87"],"state":"route-3"},{"v":"T45","state":"done"},{"v":"T55","state":"done"},{"v":"T65","state":"done"},{"v":"T66","state":"done"},{"v":"T76","state":"done"},{"v":"T77","state":"done"},{"v":"T87","state":"done"},{"v":"T88","state":"done"},{"v":"T89","state":"done"},{"v":"T90","state":"done"},{"v":"T100","state":"done"},{"panel":"candidates","list":[]},{"panel":"routes","list":[{"key":"Route 1","note":"37 min"},{"key":"Route 2","note":"41 min"},{"key":"Route 3","note":"41 min"}]},{"panel":"numbers","set":{"Routes found":"3"}},{"panel":"numbers","set":{"Candidates waiting":"0"}},{"panel":"numbers","set":{"Route 1":"37 min"}},{"panel":"numbers","set":{"Route 2":"41 min, shares 35%"}},{"panel":"numbers","set":{"Route 3":"41 min, shares 65%"}}]},{"say":"Done. The three quickest routes take 37, 41 and 41 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, \"T45\", \"T100\", 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}"}
