{"algorithm":"bidirectional","about":["Bidirectional search runs two Dijkstra searches at once: one forward from the start and one backward from the goal. Each step takes the vertex with the smaller time from the two queues, so the two sides grow at the same pace. Each side covers about half the distance, so on a road map it looks at a fraction of what one search would. Routing engines use it on its own and under faster methods such as contraction hierarchies.","The search from the goal follows edges in reverse: on a directed graph it walks the edges that lead into a vertex, so a one-way street that leads into the goal is taken backward from the goal. Each time one side reaches a vertex the other side has reached, the two times add up to a route, and the search keeps the quickest one it has found.","It can't stop the moment the two sides first touch, since a quicker route can pass through vertices neither side has settled. It stops once the two smallest times left in the queues add up to no less than the best route: any route not found yet goes through a vertex still in a queue and takes at least that long.","path.Bidirectional takes the edge cost as a function, and a nil cost uses the edge weight. A negative cost returns ErrNegativeWeight, and a goal the start can't reach returns ErrUnreachable. Ties break by the order vertices and edges were added, so the same graph gives the same route on every run."],"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 is the quickest drive from I23 to I18, when most streets are one way and the search from I18 has to follow them in reverse?","params":{"start":"I23","goal":"I18"},"result":{"kind":"route","vertices":["I23","I24","I25","I26","I17","I8","I9","I18"],"cost":26},"answer":"The quickest drive from I23 to I18 takes 26 minutes, along 7 streets.","legend":{"vertex":[{"id":"idle","label":"Not reached","color":"#64748B","shape":"hollow"},{"id":"waiting","label":"In a queue","color":"#E69F00","shape":"dashed-square"},{"id":"settled-a","label":"Settled from the start","color":"#56B4E9","shape":"filled"},{"id":"settled-b","label":"Settled from the goal","color":"#E69F00","shape":"ring"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"from-a","label":"Quickest way in from the start so far","color":"#56B4E9","shape":"thick"},{"id":"from-b","label":"Quickest way on to the goal so far","color":"#E69F00","shape":"dashed"},{"id":"examined","label":"Checked, not quicker","color":"#CC79A7","shape":"line"},{"id":"tree","label":"Quickest route","color":"#009E73","shape":"thick"}],"panels":[{"id":"queue-a","title":"Queue from the start","kind":"list"},{"id":"queue-b","title":"Queue from the goal","kind":"list"},{"id":"numbers","title":"So far","kind":"numbers"}]},"steps":[{"say":"Search forward from I23 and backward from I18 at once. Each side has its own queue, ordered by time from its end, and each round settles the vertex with the smaller time of the two.","ops":[{"v":"I23","state":"waiting"},{"v":"I18","state":"waiting"},{"panel":"queue-a","list":[{"key":"I23","note":"0"}]},{"panel":"queue-b","list":[{"key":"I18","note":"0"}]},{"panel":"numbers","set":{"Settled from the start":"0"}},{"panel":"numbers","set":{"Settled from the goal":"0"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"The next times are 0 from the start and 0 from the goal: 0 + 0 = 0, and no route is known yet, so go on. Settle I23 from the start at 0.","ops":[{"v":"I23","state":"settled-a"},{"panel":"queue-a","list":[]},{"panel":"queue-b","list":[{"key":"I18","note":"0"}]},{"panel":"numbers","set":{"Settled from the start":"1"}},{"panel":"numbers","set":{"Settled from the goal":"0"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I23 to I14: 0 + 3 = 3.","ops":[{"e":["I23","I14"],"state":"from-a"},{"v":"I14","state":"waiting"},{"panel":"queue-a","list":[{"key":"I14","note":"3"}]},{"panel":"queue-b","list":[{"key":"I18","note":"0"}]},{"panel":"numbers","set":{"Settled from the start":"1"}},{"panel":"numbers","set":{"Settled from the goal":"0"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I23 to I22: 0 + 5 = 5.","ops":[{"e":["I23","I22"],"state":"from-a"},{"v":"I22","state":"waiting"},{"panel":"queue-a","list":[{"key":"I14","note":"3"},{"key":"I22","note":"5"}]},{"panel":"queue-b","list":[{"key":"I18","note":"0"}]},{"panel":"numbers","set":{"Settled from the start":"1"}},{"panel":"numbers","set":{"Settled from the goal":"0"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I23 to I24: 0 + 5 = 5.","ops":[{"e":["I23","I24"],"state":"from-a"},{"v":"I24","state":"waiting"},{"panel":"queue-a","list":[{"key":"I14","note":"3"},{"key":"I22","note":"5"},{"key":"I24","note":"5"}]},{"panel":"queue-b","list":[{"key":"I18","note":"0"}]},{"panel":"numbers","set":{"Settled from the start":"1"}},{"panel":"numbers","set":{"Settled from the goal":"0"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I23 to I32: 0 + 5 = 5.","ops":[{"e":["I23","I32"],"state":"from-a"},{"v":"I32","state":"waiting"},{"panel":"queue-a","list":[{"key":"I14","note":"3"},{"key":"I22","note":"5"},{"key":"I24","note":"5"},{"key":"I32","note":"5"}]},{"panel":"queue-b","list":[{"key":"I18","note":"0"}]},{"panel":"numbers","set":{"Settled from the start":"1"}},{"panel":"numbers","set":{"Settled from the goal":"0"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"The next times are 3 from the start and 0 from the goal: 3 + 0 = 3, and no route is known yet, so go on. Settle I18 from the goal at 0.","ops":[{"v":"I18","state":"settled-b"},{"panel":"queue-a","list":[{"key":"I14","note":"3"},{"key":"I22","note":"5"},{"key":"I24","note":"5"},{"key":"I32","note":"5"}]},{"panel":"queue-b","list":[]},{"panel":"numbers","set":{"Settled from the start":"1"}},{"panel":"numbers","set":{"Settled from the goal":"1"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I9 to I18 leads into I18, so the search from the goal takes it backward, from I18 to I9. It follows every street in reverse, so a one-way street counts only the way it leads to the goal. 0 + 2 = 2.","ops":[{"e":["I9","I18"],"state":"from-b"},{"v":"I9","state":"waiting"},{"panel":"queue-a","list":[{"key":"I14","note":"3"},{"key":"I22","note":"5"},{"key":"I24","note":"5"},{"key":"I32","note":"5"}]},{"panel":"queue-b","list":[{"key":"I9","note":"2"}]},{"panel":"numbers","set":{"Settled from the start":"1"}},{"panel":"numbers","set":{"Settled from the goal":"1"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"The next times are 3 from the start and 2 from the goal: 3 + 2 = 5, and no route is known yet, so go on. Settle I9 from the goal at 2.","ops":[{"v":"I9","state":"settled-b"},{"panel":"queue-a","list":[{"key":"I14","note":"3"},{"key":"I22","note":"5"},{"key":"I24","note":"5"},{"key":"I32","note":"5"}]},{"panel":"queue-b","list":[]},{"panel":"numbers","set":{"Settled from the start":"1"}},{"panel":"numbers","set":{"Settled from the goal":"2"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I8 to I9 leads into I9, so the search from the goal takes it backward: 2 + 4 = 6.","ops":[{"e":["I8","I9"],"state":"from-b"},{"v":"I8","state":"waiting"},{"panel":"queue-a","list":[{"key":"I14","note":"3"},{"key":"I22","note":"5"},{"key":"I24","note":"5"},{"key":"I32","note":"5"}]},{"panel":"queue-b","list":[{"key":"I8","note":"6"}]},{"panel":"numbers","set":{"Settled from the start":"1"}},{"panel":"numbers","set":{"Settled from the goal":"2"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"The next times are 3 from the start and 6 from the goal: 3 + 6 = 9, and no route is known yet, so go on. Settle I14 from the start at 3.","ops":[{"v":"I14","state":"settled-a"},{"panel":"queue-a","list":[{"key":"I22","note":"5"},{"key":"I24","note":"5"},{"key":"I32","note":"5"}]},{"panel":"queue-b","list":[{"key":"I8","note":"6"}]},{"panel":"numbers","set":{"Settled from the start":"2"}},{"panel":"numbers","set":{"Settled from the goal":"2"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I14 to I5: 3 + 5 = 8.","ops":[{"e":["I14","I5"],"state":"from-a"},{"v":"I5","state":"waiting"},{"panel":"queue-a","list":[{"key":"I22","note":"5"},{"key":"I24","note":"5"},{"key":"I32","note":"5"},{"key":"I5","note":"8"}]},{"panel":"queue-b","list":[{"key":"I8","note":"6"}]},{"panel":"numbers","set":{"Settled from the start":"2"}},{"panel":"numbers","set":{"Settled from the goal":"2"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I14 to I13: 3 + 4 = 7.","ops":[{"e":["I14","I13"],"state":"from-a"},{"v":"I13","state":"waiting"},{"panel":"queue-a","list":[{"key":"I22","note":"5"},{"key":"I24","note":"5"},{"key":"I32","note":"5"},{"key":"I13","note":"7"},{"key":"I5","note":"8"}]},{"panel":"queue-b","list":[{"key":"I8","note":"6"}]},{"panel":"numbers","set":{"Settled from the start":"2"}},{"panel":"numbers","set":{"Settled from the goal":"2"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"The next times are 5 from the start and 6 from the goal: 5 + 6 = 11, and no route is known yet, so go on. Settle I22 from the start at 5.","ops":[{"v":"I22","state":"settled-a"},{"panel":"queue-a","list":[{"key":"I24","note":"5"},{"key":"I32","note":"5"},{"key":"I13","note":"7"},{"key":"I5","note":"8"}]},{"panel":"queue-b","list":[{"key":"I8","note":"6"}]},{"panel":"numbers","set":{"Settled from the start":"3"}},{"panel":"numbers","set":{"Settled from the goal":"2"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I22 to I21: 5 + 3 = 8.","ops":[{"e":["I22","I21"],"state":"from-a"},{"v":"I21","state":"waiting"},{"panel":"queue-a","list":[{"key":"I24","note":"5"},{"key":"I32","note":"5"},{"key":"I13","note":"7"},{"key":"I5","note":"8"},{"key":"I21","note":"8"}]},{"panel":"queue-b","list":[{"key":"I8","note":"6"}]},{"panel":"numbers","set":{"Settled from the start":"3"}},{"panel":"numbers","set":{"Settled from the goal":"2"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I22 to I31: 5 + 2 = 7.","ops":[{"e":["I22","I31"],"state":"from-a"},{"v":"I31","state":"waiting"},{"panel":"queue-a","list":[{"key":"I24","note":"5"},{"key":"I32","note":"5"},{"key":"I13","note":"7"},{"key":"I31","note":"7"},{"key":"I5","note":"8"},{"key":"I21","note":"8"}]},{"panel":"queue-b","list":[{"key":"I8","note":"6"}]},{"panel":"numbers","set":{"Settled from the start":"3"}},{"panel":"numbers","set":{"Settled from the goal":"2"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"The next times are 5 from the start and 6 from the goal: 5 + 6 = 11, and no route is known yet, so go on. Settle I24 from the start at 5.","ops":[{"v":"I24","state":"settled-a"},{"panel":"queue-a","list":[{"key":"I32","note":"5"},{"key":"I13","note":"7"},{"key":"I31","note":"7"},{"key":"I5","note":"8"},{"key":"I21","note":"8"}]},{"panel":"queue-b","list":[{"key":"I8","note":"6"}]},{"panel":"numbers","set":{"Settled from the start":"4"}},{"panel":"numbers","set":{"Settled from the goal":"2"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I24 to I15: 5 + 4 = 9.","ops":[{"e":["I24","I15"],"state":"from-a"},{"v":"I15","state":"waiting"},{"panel":"queue-a","list":[{"key":"I32","note":"5"},{"key":"I13","note":"7"},{"key":"I31","note":"7"},{"key":"I5","note":"8"},{"key":"I21","note":"8"},{"key":"I15","note":"9"}]},{"panel":"queue-b","list":[{"key":"I8","note":"6"}]},{"panel":"numbers","set":{"Settled from the start":"4"}},{"panel":"numbers","set":{"Settled from the goal":"2"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I24 to I25: 5 + 2 = 7.","ops":[{"e":["I24","I25"],"state":"from-a"},{"v":"I25","state":"waiting"},{"panel":"queue-a","list":[{"key":"I32","note":"5"},{"key":"I13","note":"7"},{"key":"I31","note":"7"},{"key":"I25","note":"7"},{"key":"I5","note":"8"},{"key":"I21","note":"8"},{"key":"I15","note":"9"}]},{"panel":"queue-b","list":[{"key":"I8","note":"6"}]},{"panel":"numbers","set":{"Settled from the start":"4"}},{"panel":"numbers","set":{"Settled from the goal":"2"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"The next times are 5 from the start and 6 from the goal: 5 + 6 = 11, and no route is known yet, so go on. Settle I32 from the start at 5.","ops":[{"v":"I32","state":"settled-a"},{"panel":"queue-a","list":[{"key":"I13","note":"7"},{"key":"I31","note":"7"},{"key":"I25","note":"7"},{"key":"I5","note":"8"},{"key":"I21","note":"8"},{"key":"I15","note":"9"}]},{"panel":"queue-b","list":[{"key":"I8","note":"6"}]},{"panel":"numbers","set":{"Settled from the start":"5"}},{"panel":"numbers","set":{"Settled from the goal":"2"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I32 to I33: 5 + 5 = 10.","ops":[{"e":["I32","I33"],"state":"from-a"},{"v":"I33","state":"waiting"},{"panel":"queue-a","list":[{"key":"I13","note":"7"},{"key":"I31","note":"7"},{"key":"I25","note":"7"},{"key":"I5","note":"8"},{"key":"I21","note":"8"},{"key":"I15","note":"9"},{"key":"I33","note":"10"}]},{"panel":"queue-b","list":[{"key":"I8","note":"6"}]},{"panel":"numbers","set":{"Settled from the start":"5"}},{"panel":"numbers","set":{"Settled from the goal":"2"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I32 to I41: 5 + 4 = 9.","ops":[{"e":["I32","I41"],"state":"from-a"},{"v":"I41","state":"waiting"},{"panel":"queue-a","list":[{"key":"I13","note":"7"},{"key":"I31","note":"7"},{"key":"I25","note":"7"},{"key":"I5","note":"8"},{"key":"I21","note":"8"},{"key":"I15","note":"9"},{"key":"I41","note":"9"},{"key":"I33","note":"10"}]},{"panel":"queue-b","list":[{"key":"I8","note":"6"}]},{"panel":"numbers","set":{"Settled from the start":"5"}},{"panel":"numbers","set":{"Settled from the goal":"2"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"The next times are 7 from the start and 6 from the goal: 7 + 6 = 13, and no route is known yet, so go on. Settle I8 from the goal at 6.","ops":[{"v":"I8","state":"settled-b"},{"panel":"queue-a","list":[{"key":"I13","note":"7"},{"key":"I31","note":"7"},{"key":"I25","note":"7"},{"key":"I5","note":"8"},{"key":"I21","note":"8"},{"key":"I15","note":"9"},{"key":"I41","note":"9"},{"key":"I33","note":"10"}]},{"panel":"queue-b","list":[]},{"panel":"numbers","set":{"Settled from the start":"5"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I7 to I8 leads into I8, so the search from the goal takes it backward: 6 + 4 = 10.","ops":[{"e":["I7","I8"],"state":"from-b"},{"v":"I7","state":"waiting"},{"panel":"queue-a","list":[{"key":"I13","note":"7"},{"key":"I31","note":"7"},{"key":"I25","note":"7"},{"key":"I5","note":"8"},{"key":"I21","note":"8"},{"key":"I15","note":"9"},{"key":"I41","note":"9"},{"key":"I33","note":"10"}]},{"panel":"queue-b","list":[{"key":"I7","note":"10"}]},{"panel":"numbers","set":{"Settled from the start":"5"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I17 to I8 leads into I8, so the search from the goal takes it backward: 6 + 5 = 11.","ops":[{"e":["I17","I8"],"state":"from-b"},{"v":"I17","state":"waiting"},{"panel":"queue-a","list":[{"key":"I13","note":"7"},{"key":"I31","note":"7"},{"key":"I25","note":"7"},{"key":"I5","note":"8"},{"key":"I21","note":"8"},{"key":"I15","note":"9"},{"key":"I41","note":"9"},{"key":"I33","note":"10"}]},{"panel":"queue-b","list":[{"key":"I7","note":"10"},{"key":"I17","note":"11"}]},{"panel":"numbers","set":{"Settled from the start":"5"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"The next times are 7 from the start and 10 from the goal: 7 + 10 = 17, and no route is known yet, so go on. Settle I13 from the start at 7.","ops":[{"v":"I13","state":"settled-a"},{"panel":"queue-a","list":[{"key":"I31","note":"7"},{"key":"I25","note":"7"},{"key":"I5","note":"8"},{"key":"I21","note":"8"},{"key":"I15","note":"9"},{"key":"I41","note":"9"},{"key":"I33","note":"10"}]},{"panel":"queue-b","list":[{"key":"I7","note":"10"},{"key":"I17","note":"11"}]},{"panel":"numbers","set":{"Settled from the start":"6"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I13 to I12: 7 + 5 = 12.","ops":[{"e":["I13","I12"],"state":"from-a"},{"v":"I12","state":"waiting"},{"panel":"queue-a","list":[{"key":"I31","note":"7"},{"key":"I25","note":"7"},{"key":"I5","note":"8"},{"key":"I21","note":"8"},{"key":"I15","note":"9"},{"key":"I41","note":"9"},{"key":"I33","note":"10"},{"key":"I12","note":"12"}]},{"panel":"queue-b","list":[{"key":"I7","note":"10"},{"key":"I17","note":"11"}]},{"panel":"numbers","set":{"Settled from the start":"6"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"The next times are 7 from the start and 10 from the goal: 7 + 10 = 17, and no route is known yet, so go on. Settle I31 from the start at 7.","ops":[{"v":"I31","state":"settled-a"},{"panel":"queue-a","list":[{"key":"I25","note":"7"},{"key":"I5","note":"8"},{"key":"I21","note":"8"},{"key":"I15","note":"9"},{"key":"I41","note":"9"},{"key":"I33","note":"10"},{"key":"I12","note":"12"}]},{"panel":"queue-b","list":[{"key":"I7","note":"10"},{"key":"I17","note":"11"}]},{"panel":"numbers","set":{"Settled from the start":"7"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I31 to I40: 7 + 3 = 10.","ops":[{"e":["I31","I40"],"state":"from-a"},{"v":"I40","state":"waiting"},{"panel":"queue-a","list":[{"key":"I25","note":"7"},{"key":"I5","note":"8"},{"key":"I21","note":"8"},{"key":"I15","note":"9"},{"key":"I41","note":"9"},{"key":"I33","note":"10"},{"key":"I40","note":"10"},{"key":"I12","note":"12"}]},{"panel":"queue-b","list":[{"key":"I7","note":"10"},{"key":"I17","note":"11"}]},{"panel":"numbers","set":{"Settled from the start":"7"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"The next times are 7 from the start and 10 from the goal: 7 + 10 = 17, and no route is known yet, so go on. Settle I25 from the start at 7.","ops":[{"v":"I25","state":"settled-a"},{"panel":"queue-a","list":[{"key":"I5","note":"8"},{"key":"I21","note":"8"},{"key":"I15","note":"9"},{"key":"I41","note":"9"},{"key":"I33","note":"10"},{"key":"I40","note":"10"},{"key":"I12","note":"12"}]},{"panel":"queue-b","list":[{"key":"I7","note":"10"},{"key":"I17","note":"11"}]},{"panel":"numbers","set":{"Settled from the start":"8"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I25 to I26: 7 + 4 = 11.","ops":[{"e":["I25","I26"],"state":"from-a"},{"v":"I26","state":"waiting"},{"panel":"queue-a","list":[{"key":"I5","note":"8"},{"key":"I21","note":"8"},{"key":"I15","note":"9"},{"key":"I41","note":"9"},{"key":"I33","note":"10"},{"key":"I40","note":"10"},{"key":"I26","note":"11"},{"key":"I12","note":"12"}]},{"panel":"queue-b","list":[{"key":"I7","note":"10"},{"key":"I17","note":"11"}]},{"panel":"numbers","set":{"Settled from the start":"8"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I25 to I34: 7 + 3 = 10.","ops":[{"e":["I25","I34"],"state":"from-a"},{"v":"I34","state":"waiting"},{"panel":"queue-a","list":[{"key":"I5","note":"8"},{"key":"I21","note":"8"},{"key":"I15","note":"9"},{"key":"I41","note":"9"},{"key":"I33","note":"10"},{"key":"I40","note":"10"},{"key":"I34","note":"10"},{"key":"I26","note":"11"},{"key":"I12","note":"12"}]},{"panel":"queue-b","list":[{"key":"I7","note":"10"},{"key":"I17","note":"11"}]},{"panel":"numbers","set":{"Settled from the start":"8"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"The next times are 8 from the start and 10 from the goal: 8 + 10 = 18, and no route is known yet, so go on. Settle I5 from the start at 8.","ops":[{"v":"I5","state":"settled-a"},{"panel":"queue-a","list":[{"key":"I21","note":"8"},{"key":"I15","note":"9"},{"key":"I41","note":"9"},{"key":"I33","note":"10"},{"key":"I40","note":"10"},{"key":"I34","note":"10"},{"key":"I26","note":"11"},{"key":"I12","note":"12"}]},{"panel":"queue-b","list":[{"key":"I7","note":"10"},{"key":"I17","note":"11"}]},{"panel":"numbers","set":{"Settled from the start":"9"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I5 to I6: 8 + 5 = 13.","ops":[{"e":["I5","I6"],"state":"from-a"},{"v":"I6","state":"waiting"},{"panel":"queue-a","list":[{"key":"I21","note":"8"},{"key":"I15","note":"9"},{"key":"I41","note":"9"},{"key":"I33","note":"10"},{"key":"I40","note":"10"},{"key":"I34","note":"10"},{"key":"I26","note":"11"},{"key":"I12","note":"12"},{"key":"I6","note":"13"}]},{"panel":"queue-b","list":[{"key":"I7","note":"10"},{"key":"I17","note":"11"}]},{"panel":"numbers","set":{"Settled from the start":"9"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"The next times are 8 from the start and 10 from the goal: 8 + 10 = 18, and no route is known yet, so go on. Settle I21 from the start at 8.","ops":[{"v":"I21","state":"settled-a"},{"panel":"queue-a","list":[{"key":"I15","note":"9"},{"key":"I41","note":"9"},{"key":"I33","note":"10"},{"key":"I40","note":"10"},{"key":"I34","note":"10"},{"key":"I26","note":"11"},{"key":"I12","note":"12"},{"key":"I6","note":"13"}]},{"panel":"queue-b","list":[{"key":"I7","note":"10"},{"key":"I17","note":"11"}]},{"panel":"numbers","set":{"Settled from the start":"10"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I21 to I12: 8 + 2 = 10.","ops":[{"e":["I21","I12"],"state":"from-a"},{"v":"I12","state":"waiting"},{"e":["I13","I12"],"state":"examined"},{"panel":"queue-a","list":[{"key":"I15","note":"9"},{"key":"I41","note":"9"},{"key":"I33","note":"10"},{"key":"I40","note":"10"},{"key":"I34","note":"10"},{"key":"I12","note":"10"},{"key":"I26","note":"11"},{"key":"I6","note":"13"}]},{"panel":"queue-b","list":[{"key":"I7","note":"10"},{"key":"I17","note":"11"}]},{"panel":"numbers","set":{"Settled from the start":"10"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I21 to I20: 8 + 2 = 10.","ops":[{"e":["I21","I20"],"state":"from-a"},{"v":"I20","state":"waiting"},{"panel":"queue-a","list":[{"key":"I15","note":"9"},{"key":"I41","note":"9"},{"key":"I33","note":"10"},{"key":"I40","note":"10"},{"key":"I34","note":"10"},{"key":"I12","note":"10"},{"key":"I20","note":"10"},{"key":"I26","note":"11"},{"key":"I6","note":"13"}]},{"panel":"queue-b","list":[{"key":"I7","note":"10"},{"key":"I17","note":"11"}]},{"panel":"numbers","set":{"Settled from the start":"10"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"The next times are 9 from the start and 10 from the goal: 9 + 10 = 19, and no route is known yet, so go on. Settle I15 from the start at 9.","ops":[{"v":"I15","state":"settled-a"},{"panel":"queue-a","list":[{"key":"I41","note":"9"},{"key":"I33","note":"10"},{"key":"I40","note":"10"},{"key":"I34","note":"10"},{"key":"I12","note":"10"},{"key":"I20","note":"10"},{"key":"I26","note":"11"},{"key":"I6","note":"13"}]},{"panel":"queue-b","list":[{"key":"I7","note":"10"},{"key":"I17","note":"11"}]},{"panel":"numbers","set":{"Settled from the start":"11"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I15 to I6: 9 + 4 = 13, not quicker than 13.","ops":[{"e":["I15","I6"],"state":"examined"}]},{"say":"The next times are 9 from the start and 10 from the goal: 9 + 10 = 19, and no route is known yet, so go on. Settle I41 from the start at 9.","ops":[{"v":"I41","state":"settled-a"},{"panel":"queue-a","list":[{"key":"I33","note":"10"},{"key":"I40","note":"10"},{"key":"I34","note":"10"},{"key":"I12","note":"10"},{"key":"I20","note":"10"},{"key":"I26","note":"11"},{"key":"I6","note":"13"}]},{"panel":"queue-b","list":[{"key":"I7","note":"10"},{"key":"I17","note":"11"}]},{"panel":"numbers","set":{"Settled from the start":"12"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I41 to I40: 9 + 2 = 11, not quicker than 10.","ops":[{"e":["I41","I40"],"state":"examined"}]},{"say":"The next times are 10 from the start and 10 from the goal: 10 + 10 = 20, and no route is known yet, so go on. Settle I33 from the start at 10.","ops":[{"v":"I33","state":"settled-a"},{"panel":"queue-a","list":[{"key":"I40","note":"10"},{"key":"I34","note":"10"},{"key":"I12","note":"10"},{"key":"I20","note":"10"},{"key":"I26","note":"11"},{"key":"I6","note":"13"}]},{"panel":"queue-b","list":[{"key":"I7","note":"10"},{"key":"I17","note":"11"}]},{"panel":"numbers","set":{"Settled from the start":"13"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I33 to I34: 10 + 3 = 13, not quicker than 10.","ops":[{"e":["I33","I34"],"state":"examined"}]},{"say":"The next times are 10 from the start and 10 from the goal: 10 + 10 = 20, and no route is known yet, so go on. Settle I40 from the start at 10.","ops":[{"v":"I40","state":"settled-a"},{"panel":"queue-a","list":[{"key":"I34","note":"10"},{"key":"I12","note":"10"},{"key":"I20","note":"10"},{"key":"I26","note":"11"},{"key":"I6","note":"13"}]},{"panel":"queue-b","list":[{"key":"I7","note":"10"},{"key":"I17","note":"11"}]},{"panel":"numbers","set":{"Settled from the start":"14"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I40 to I39: 10 + 2 = 12.","ops":[{"e":["I40","I39"],"state":"from-a"},{"v":"I39","state":"waiting"},{"panel":"queue-a","list":[{"key":"I34","note":"10"},{"key":"I12","note":"10"},{"key":"I20","note":"10"},{"key":"I26","note":"11"},{"key":"I39","note":"12"},{"key":"I6","note":"13"}]},{"panel":"queue-b","list":[{"key":"I7","note":"10"},{"key":"I17","note":"11"}]},{"panel":"numbers","set":{"Settled from the start":"14"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"The next times are 10 from the start and 10 from the goal: 10 + 10 = 20, and no route is known yet, so go on. Settle I34 from the start at 10.","ops":[{"v":"I34","state":"settled-a"},{"panel":"queue-a","list":[{"key":"I12","note":"10"},{"key":"I20","note":"10"},{"key":"I26","note":"11"},{"key":"I39","note":"12"},{"key":"I6","note":"13"}]},{"panel":"queue-b","list":[{"key":"I7","note":"10"},{"key":"I17","note":"11"}]},{"panel":"numbers","set":{"Settled from the start":"15"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I34 to I35: 10 + 5 = 15.","ops":[{"e":["I34","I35"],"state":"from-a"},{"v":"I35","state":"waiting"},{"panel":"queue-a","list":[{"key":"I12","note":"10"},{"key":"I20","note":"10"},{"key":"I26","note":"11"},{"key":"I39","note":"12"},{"key":"I6","note":"13"},{"key":"I35","note":"15"}]},{"panel":"queue-b","list":[{"key":"I7","note":"10"},{"key":"I17","note":"11"}]},{"panel":"numbers","set":{"Settled from the start":"15"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I34 to I43: 10 + 3 = 13.","ops":[{"e":["I34","I43"],"state":"from-a"},{"v":"I43","state":"waiting"},{"panel":"queue-a","list":[{"key":"I12","note":"10"},{"key":"I20","note":"10"},{"key":"I26","note":"11"},{"key":"I39","note":"12"},{"key":"I6","note":"13"},{"key":"I43","note":"13"},{"key":"I35","note":"15"}]},{"panel":"queue-b","list":[{"key":"I7","note":"10"},{"key":"I17","note":"11"}]},{"panel":"numbers","set":{"Settled from the start":"15"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"The next times are 10 from the start and 10 from the goal: 10 + 10 = 20, and no route is known yet, so go on. Settle I12 from the start at 10.","ops":[{"v":"I12","state":"settled-a"},{"panel":"queue-a","list":[{"key":"I20","note":"10"},{"key":"I26","note":"11"},{"key":"I39","note":"12"},{"key":"I6","note":"13"},{"key":"I43","note":"13"},{"key":"I35","note":"15"}]},{"panel":"queue-b","list":[{"key":"I7","note":"10"},{"key":"I17","note":"11"}]},{"panel":"numbers","set":{"Settled from the start":"16"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I12 to I3: 10 + 4 = 14.","ops":[{"e":["I12","I3"],"state":"from-a"},{"v":"I3","state":"waiting"},{"panel":"queue-a","list":[{"key":"I20","note":"10"},{"key":"I26","note":"11"},{"key":"I39","note":"12"},{"key":"I6","note":"13"},{"key":"I43","note":"13"},{"key":"I3","note":"14"},{"key":"I35","note":"15"}]},{"panel":"queue-b","list":[{"key":"I7","note":"10"},{"key":"I17","note":"11"}]},{"panel":"numbers","set":{"Settled from the start":"16"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I12 to I11: 10 + 5 = 15.","ops":[{"e":["I12","I11"],"state":"from-a"},{"v":"I11","state":"waiting"},{"panel":"queue-a","list":[{"key":"I20","note":"10"},{"key":"I26","note":"11"},{"key":"I39","note":"12"},{"key":"I6","note":"13"},{"key":"I43","note":"13"},{"key":"I3","note":"14"},{"key":"I35","note":"15"},{"key":"I11","note":"15"}]},{"panel":"queue-b","list":[{"key":"I7","note":"10"},{"key":"I17","note":"11"}]},{"panel":"numbers","set":{"Settled from the start":"16"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"The next times are 10 from the start and 10 from the goal: 10 + 10 = 20, and no route is known yet, so go on. Settle I20 from the start at 10.","ops":[{"v":"I20","state":"settled-a"},{"panel":"queue-a","list":[{"key":"I26","note":"11"},{"key":"I39","note":"12"},{"key":"I6","note":"13"},{"key":"I43","note":"13"},{"key":"I3","note":"14"},{"key":"I35","note":"15"},{"key":"I11","note":"15"}]},{"panel":"queue-b","list":[{"key":"I7","note":"10"},{"key":"I17","note":"11"}]},{"panel":"numbers","set":{"Settled from the start":"17"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I20 to I19: 10 + 3 = 13.","ops":[{"e":["I20","I19"],"state":"from-a"},{"v":"I19","state":"waiting"},{"panel":"queue-a","list":[{"key":"I26","note":"11"},{"key":"I39","note":"12"},{"key":"I6","note":"13"},{"key":"I43","note":"13"},{"key":"I19","note":"13"},{"key":"I3","note":"14"},{"key":"I35","note":"15"},{"key":"I11","note":"15"}]},{"panel":"queue-b","list":[{"key":"I7","note":"10"},{"key":"I17","note":"11"}]},{"panel":"numbers","set":{"Settled from the start":"17"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I20 to I29: 10 + 3 = 13.","ops":[{"e":["I20","I29"],"state":"from-a"},{"v":"I29","state":"waiting"},{"panel":"queue-a","list":[{"key":"I26","note":"11"},{"key":"I39","note":"12"},{"key":"I6","note":"13"},{"key":"I43","note":"13"},{"key":"I19","note":"13"},{"key":"I29","note":"13"},{"key":"I3","note":"14"},{"key":"I35","note":"15"},{"key":"I11","note":"15"}]},{"panel":"queue-b","list":[{"key":"I7","note":"10"},{"key":"I17","note":"11"}]},{"panel":"numbers","set":{"Settled from the start":"17"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"The next times are 11 from the start and 10 from the goal: 11 + 10 = 21, and no route is known yet, so go on. Settle I7 from the goal at 10.","ops":[{"v":"I7","state":"settled-b"},{"panel":"queue-a","list":[{"key":"I26","note":"11"},{"key":"I39","note":"12"},{"key":"I6","note":"13"},{"key":"I43","note":"13"},{"key":"I19","note":"13"},{"key":"I29","note":"13"},{"key":"I3","note":"14"},{"key":"I35","note":"15"},{"key":"I11","note":"15"}]},{"panel":"queue-b","list":[{"key":"I17","note":"11"}]},{"panel":"numbers","set":{"Settled from the start":"17"}},{"panel":"numbers","set":{"Settled from the goal":"4"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I6 to I7 leads into I7, so the search from the goal takes it backward: 10 + 4 = 14. The other side has reached I6 at 13, so a route goes through it: 14 + 13 = 27, the best so far.","ops":[{"e":["I6","I7"],"state":"from-b"},{"v":"I6","state":"waiting"},{"panel":"queue-a","list":[{"key":"I26","note":"11"},{"key":"I39","note":"12"},{"key":"I6","note":"13"},{"key":"I43","note":"13"},{"key":"I19","note":"13"},{"key":"I29","note":"13"},{"key":"I3","note":"14"},{"key":"I35","note":"15"},{"key":"I11","note":"15"}]},{"panel":"queue-b","list":[{"key":"I17","note":"11"},{"key":"I6","note":"14"}]},{"panel":"numbers","set":{"Settled from the start":"17"}},{"panel":"numbers","set":{"Settled from the goal":"4"}},{"panel":"numbers","set":{"Best route so far":"27 min, through I6"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"The next times are 11 from the start and 11 from the goal: 11 + 11 = 22, less than the best route, 27, so a quicker one may still pass through a vertex in a queue. Go on. Settle I26 from the start at 11.","ops":[{"v":"I26","state":"settled-a"},{"panel":"queue-a","list":[{"key":"I39","note":"12"},{"key":"I6","note":"13"},{"key":"I43","note":"13"},{"key":"I19","note":"13"},{"key":"I29","note":"13"},{"key":"I3","note":"14"},{"key":"I35","note":"15"},{"key":"I11","note":"15"}]},{"panel":"queue-b","list":[{"key":"I17","note":"11"},{"key":"I6","note":"14"}]},{"panel":"numbers","set":{"Settled from the start":"18"}},{"panel":"numbers","set":{"Settled from the goal":"4"}},{"panel":"numbers","set":{"Best route so far":"27 min, through I6"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I26 to I17: 11 + 4 = 15. The other side has reached I17 at 11, so a route goes through it: 15 + 11 = 26, the best so far.","ops":[{"e":["I26","I17"],"state":"from-a"},{"v":"I17","state":"waiting"},{"panel":"queue-a","list":[{"key":"I39","note":"12"},{"key":"I6","note":"13"},{"key":"I43","note":"13"},{"key":"I19","note":"13"},{"key":"I29","note":"13"},{"key":"I3","note":"14"},{"key":"I35","note":"15"},{"key":"I11","note":"15"},{"key":"I17","note":"15"}]},{"panel":"queue-b","list":[{"key":"I17","note":"11"},{"key":"I6","note":"14"}]},{"panel":"numbers","set":{"Settled from the start":"18"}},{"panel":"numbers","set":{"Settled from the goal":"4"}},{"panel":"numbers","set":{"Best route so far":"26 min, through I17"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I26 to I27: 11 + 5 = 16.","ops":[{"e":["I26","I27"],"state":"from-a"},{"v":"I27","state":"waiting"},{"panel":"queue-a","list":[{"key":"I39","note":"12"},{"key":"I6","note":"13"},{"key":"I43","note":"13"},{"key":"I19","note":"13"},{"key":"I29","note":"13"},{"key":"I3","note":"14"},{"key":"I35","note":"15"},{"key":"I11","note":"15"},{"key":"I17","note":"15"},{"key":"I27","note":"16"}]},{"panel":"queue-b","list":[{"key":"I17","note":"11"},{"key":"I6","note":"14"}]},{"panel":"numbers","set":{"Settled from the start":"18"}},{"panel":"numbers","set":{"Settled from the goal":"4"}},{"panel":"numbers","set":{"Best route so far":"26 min, through I17"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"The next times are 12 from the start and 11 from the goal: 12 + 11 = 23, less than the best route, 26, so a quicker one may still pass through a vertex in a queue. Go on. Settle I17 from the goal at 11.","ops":[{"v":"I17","state":"settled-b"},{"panel":"queue-a","list":[{"key":"I39","note":"12"},{"key":"I6","note":"13"},{"key":"I43","note":"13"},{"key":"I19","note":"13"},{"key":"I29","note":"13"},{"key":"I3","note":"14"},{"key":"I35","note":"15"},{"key":"I11","note":"15"},{"key":"I17","note":"15"},{"key":"I27","note":"16"}]},{"panel":"queue-b","list":[{"key":"I6","note":"14"}]},{"panel":"numbers","set":{"Settled from the start":"18"}},{"panel":"numbers","set":{"Settled from the goal":"5"}},{"panel":"numbers","set":{"Best route so far":"26 min, through I17"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"I26 to I17 leads into I17, so the search from the goal takes it backward: 11 + 4 = 15. The other side has reached I26 at 11 too, but 15 + 11 = 26 is no quicker than 26.","ops":[{"e":["I26","I17"],"state":"from-b"},{"panel":"queue-a","list":[{"key":"I39","note":"12"},{"key":"I6","note":"13"},{"key":"I43","note":"13"},{"key":"I19","note":"13"},{"key":"I29","note":"13"},{"key":"I3","note":"14"},{"key":"I35","note":"15"},{"key":"I11","note":"15"},{"key":"I17","note":"15"},{"key":"I27","note":"16"}]},{"panel":"queue-b","list":[{"key":"I6","note":"14"},{"key":"I26","note":"15"}]},{"panel":"numbers","set":{"Settled from the start":"18"}},{"panel":"numbers","set":{"Settled from the goal":"5"}},{"panel":"numbers","set":{"Best route so far":"26 min, through I17"}},{"panel":"numbers","set":{"A* settles":"33"}},{"panel":"numbers","set":{"Dijkstra settles":"45"}}]},{"say":"Stop: the next times, 12 from the start and 14 from the goal, add up to 26, no less than the best route, 26, so no route left to find can be quicker. The quickest route meets at I17 and takes 26 minutes. The searches settled 18 vertices from the start and 5 from the goal.","ops":[{"e":["I23","I24"],"state":"tree"},{"e":["I24","I25"],"state":"tree"},{"e":["I25","I26"],"state":"tree"},{"e":["I26","I17"],"state":"tree"},{"e":["I17","I8"],"state":"tree"},{"e":["I8","I9"],"state":"tree"},{"e":["I9","I18"],"state":"tree"}]}],"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":"route, minutes, err := path.Bidirectional(g, \"I23\", \"I18\", nil)\nif err != nil {\n\treturn err // path.ErrUnreachable when the goal is out of reach\n}\nfmt.Println(minutes)\nfor _, v := range route {\n\tfmt.Println(v.Label())\n}"}
