{"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":"school-run","name":"School run","description":"Six places on the morning drive to school. Most streets go both ways, and each edge is the travel time in minutes.","family":"road","directed":true,"weighted":true,"acyclic":false,"vertices":[{"id":"Home","x":128,"y":320},{"id":"Bakery","x":352,"y":160},{"id":"Bridge","x":352,"y":480},{"id":"Park","x":608,"y":320},{"id":"Library","x":832,"y":160},{"id":"School","x":864,"y":448}],"edges":[{"from":"Home","to":"Bakery","weight":4},{"from":"Bakery","to":"Home","weight":4},{"from":"Home","to":"Bridge","weight":3},{"from":"Bridge","to":"Home","weight":3},{"from":"Bakery","to":"Park","weight":3},{"from":"Park","to":"Bakery","weight":3},{"from":"Bridge","to":"Park","weight":2},{"from":"Park","to":"Bridge","weight":2},{"from":"Park","to":"Library","weight":4},{"from":"Library","to":"Park","weight":4},{"from":"Park","to":"School","weight":7},{"from":"Library","to":"School","weight":2},{"from":"School","to":"Library","weight":2}],"details":{"vertices":6,"edges":13,"directed":true,"weighted":true,"acyclic":false,"weightMin":2,"weightMax":7,"negativeWeights":false,"density":0.43333333333333335,"inDegree":{"min":2,"avg":2.1666666666666665,"max":3},"outDegree":{"min":1,"avg":2.1666666666666665,"max":4},"selfLoops":0,"components":1}},"problem":"What is the quickest drive from home to school, searching from home and from the school at once?","params":{"start":"Home","goal":"School"},"result":{"kind":"route","vertices":["Home","Bridge","Park","Library","School"],"cost":11},"answer":"The quickest drive from Home to School takes 11 minutes, along 4 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 Home and backward from School 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":"Home","state":"waiting"},{"v":"School","state":"waiting"},{"panel":"queue-a","list":[{"key":"Home","note":"0"}]},{"panel":"queue-b","list":[{"key":"School","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":"6"}},{"panel":"numbers","set":{"Dijkstra settles":"6"}}]},{"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 Home from the start at 0.","ops":[{"v":"Home","state":"settled-a"},{"panel":"queue-a","list":[]},{"panel":"queue-b","list":[{"key":"School","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":"6"}},{"panel":"numbers","set":{"Dijkstra settles":"6"}}]},{"say":"Home to Bakery: 0 + 4 = 4.","ops":[{"e":["Home","Bakery"],"state":"from-a"},{"v":"Bakery","state":"waiting"},{"panel":"queue-a","list":[{"key":"Bakery","note":"4"}]},{"panel":"queue-b","list":[{"key":"School","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":"6"}},{"panel":"numbers","set":{"Dijkstra settles":"6"}}]},{"say":"Home to Bridge: 0 + 3 = 3.","ops":[{"e":["Home","Bridge"],"state":"from-a"},{"v":"Bridge","state":"waiting"},{"panel":"queue-a","list":[{"key":"Bridge","note":"3"},{"key":"Bakery","note":"4"}]},{"panel":"queue-b","list":[{"key":"School","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":"6"}},{"panel":"numbers","set":{"Dijkstra settles":"6"}}]},{"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 School from the goal at 0.","ops":[{"v":"School","state":"settled-b"},{"panel":"queue-a","list":[{"key":"Bridge","note":"3"},{"key":"Bakery","note":"4"}]},{"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":"6"}},{"panel":"numbers","set":{"Dijkstra settles":"6"}}]},{"say":"Park to School leads into School, so the search from the goal takes it backward, from School to Park. It follows every street in reverse, so a one-way street counts only the way it leads to the goal. 0 + 7 = 7.","ops":[{"e":["Park","School"],"state":"from-b"},{"v":"Park","state":"waiting"},{"panel":"queue-a","list":[{"key":"Bridge","note":"3"},{"key":"Bakery","note":"4"}]},{"panel":"queue-b","list":[{"key":"Park","note":"7"}]},{"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":"6"}},{"panel":"numbers","set":{"Dijkstra settles":"6"}}]},{"say":"Library to School leads into School, so the search from the goal takes it backward: 0 + 2 = 2.","ops":[{"e":["Library","School"],"state":"from-b"},{"v":"Library","state":"waiting"},{"panel":"queue-a","list":[{"key":"Bridge","note":"3"},{"key":"Bakery","note":"4"}]},{"panel":"queue-b","list":[{"key":"Library","note":"2"},{"key":"Park","note":"7"}]},{"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":"6"}},{"panel":"numbers","set":{"Dijkstra settles":"6"}}]},{"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 Library from the goal at 2.","ops":[{"v":"Library","state":"settled-b"},{"panel":"queue-a","list":[{"key":"Bridge","note":"3"},{"key":"Bakery","note":"4"}]},{"panel":"queue-b","list":[{"key":"Park","note":"7"}]},{"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":"6"}},{"panel":"numbers","set":{"Dijkstra settles":"6"}}]},{"say":"Park to Library leads into Library, so the search from the goal takes it backward: 2 + 4 = 6.","ops":[{"e":["Park","Library"],"state":"from-b"},{"v":"Park","state":"waiting"},{"e":["Park","School"],"state":"examined"},{"panel":"queue-a","list":[{"key":"Bridge","note":"3"},{"key":"Bakery","note":"4"}]},{"panel":"queue-b","list":[{"key":"Park","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":"6"}},{"panel":"numbers","set":{"Dijkstra settles":"6"}}]},{"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 Bridge from the start at 3.","ops":[{"v":"Bridge","state":"settled-a"},{"panel":"queue-a","list":[{"key":"Bakery","note":"4"}]},{"panel":"queue-b","list":[{"key":"Park","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":"6"}},{"panel":"numbers","set":{"Dijkstra settles":"6"}}]},{"say":"Bridge to Park: 3 + 2 = 5. The other side has reached Park at 6, so a route goes through it: 5 + 6 = 11, the best so far.","ops":[{"e":["Bridge","Park"],"state":"from-a"},{"v":"Park","state":"waiting"},{"panel":"queue-a","list":[{"key":"Bakery","note":"4"},{"key":"Park","note":"5"}]},{"panel":"queue-b","list":[{"key":"Park","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":"11 min, through Park"}},{"panel":"numbers","set":{"A* settles":"6"}},{"panel":"numbers","set":{"Dijkstra settles":"6"}}]},{"say":"The next times are 4 from the start and 6 from the goal: 4 + 6 = 10, less than the best route, 11, so a quicker one may still pass through a vertex in a queue. Go on. Settle Bakery from the start at 4.","ops":[{"v":"Bakery","state":"settled-a"},{"panel":"queue-a","list":[{"key":"Park","note":"5"}]},{"panel":"queue-b","list":[{"key":"Park","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":"11 min, through Park"}},{"panel":"numbers","set":{"A* settles":"6"}},{"panel":"numbers","set":{"Dijkstra settles":"6"}}]},{"say":"Bakery to Park: 4 + 3 = 7, not quicker than 5.","ops":[{"e":["Bakery","Park"],"state":"examined"}]},{"say":"Stop: the next times, 5 from the start and 6 from the goal, add up to 11, no less than the best route, 11, so no route left to find can be quicker. The quickest route meets at Park and takes 11 minutes. The searches settled 3 vertices from the start and 2 from the goal.","ops":[{"e":["Home","Bridge"],"state":"tree"},{"e":["Bridge","Park"],"state":"tree"},{"e":["Park","Library"],"state":"tree"},{"e":["Library","School"],"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, \"Home\", \"School\", 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}"}
