{"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":"delivery-area","name":"Delivery area","description":"Eight stops in a small town. Streets are one way, and each edge is the travel time in minutes.","family":"road","directed":true,"weighted":true,"acyclic":false,"vertices":[{"id":"Depot","x":128,"y":320},{"id":"Bakery","x":352,"y":128},{"id":"Market","x":352,"y":512},{"id":"School","x":608,"y":128},{"id":"Park","x":608,"y":352},{"id":"Clinic","x":608,"y":544},{"id":"Library","x":832,"y":224},{"id":"Station","x":864,"y":480}],"edges":[{"from":"Depot","to":"Bakery","weight":4},{"from":"Depot","to":"Market","weight":2},{"from":"Market","to":"Bakery","weight":1},{"from":"Bakery","to":"School","weight":5},{"from":"Bakery","to":"Park","weight":7},{"from":"Market","to":"Park","weight":8},{"from":"Market","to":"Clinic","weight":10},{"from":"School","to":"Library","weight":3},{"from":"Park","to":"Library","weight":2},{"from":"Park","to":"Station","weight":6},{"from":"Clinic","to":"Station","weight":2},{"from":"Library","to":"Station","weight":5}],"details":{"vertices":8,"edges":12,"directed":true,"weighted":true,"acyclic":true,"weightMin":1,"weightMax":10,"negativeWeights":false,"density":0.21428571428571427,"inDegree":{"min":0,"avg":1.5,"max":3},"outDegree":{"min":0,"avg":1.5,"max":3},"selfLoops":0,"components":1}},"problem":"What is the quickest drive from the depot to the station, searching from both ends at once?","params":{"start":"Depot","goal":"Station"},"result":{"kind":"route","vertices":["Depot","Market","Clinic","Station"],"cost":14},"answer":"The quickest drive from Depot to Station takes 14 minutes, along 3 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 Depot and backward from Station 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":"Depot","state":"waiting"},{"v":"Station","state":"waiting"},{"panel":"queue-a","list":[{"key":"Depot","note":"0"}]},{"panel":"queue-b","list":[{"key":"Station","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":"8"}},{"panel":"numbers","set":{"Dijkstra settles":"8"}}]},{"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 Depot from the start at 0.","ops":[{"v":"Depot","state":"settled-a"},{"panel":"queue-a","list":[]},{"panel":"queue-b","list":[{"key":"Station","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":"8"}},{"panel":"numbers","set":{"Dijkstra settles":"8"}}]},{"say":"Depot to Bakery: 0 + 4 = 4.","ops":[{"e":["Depot","Bakery"],"state":"from-a"},{"v":"Bakery","state":"waiting"},{"panel":"queue-a","list":[{"key":"Bakery","note":"4"}]},{"panel":"queue-b","list":[{"key":"Station","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":"8"}},{"panel":"numbers","set":{"Dijkstra settles":"8"}}]},{"say":"Depot to Market: 0 + 2 = 2.","ops":[{"e":["Depot","Market"],"state":"from-a"},{"v":"Market","state":"waiting"},{"panel":"queue-a","list":[{"key":"Market","note":"2"},{"key":"Bakery","note":"4"}]},{"panel":"queue-b","list":[{"key":"Station","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":"8"}},{"panel":"numbers","set":{"Dijkstra settles":"8"}}]},{"say":"The next times are 2 from the start and 0 from the goal: 2 + 0 = 2, and no route is known yet, so go on. Settle Station from the goal at 0.","ops":[{"v":"Station","state":"settled-b"},{"panel":"queue-a","list":[{"key":"Market","note":"2"},{"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":"8"}},{"panel":"numbers","set":{"Dijkstra settles":"8"}}]},{"say":"Park to Station leads into Station, so the search from the goal takes it backward, from Station to Park. It follows every street in reverse, so a one-way street counts only the way it leads to the goal. 0 + 6 = 6.","ops":[{"e":["Park","Station"],"state":"from-b"},{"v":"Park","state":"waiting"},{"panel":"queue-a","list":[{"key":"Market","note":"2"},{"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":"1"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"8"}},{"panel":"numbers","set":{"Dijkstra settles":"8"}}]},{"say":"Clinic to Station leads into Station, so the search from the goal takes it backward: 0 + 2 = 2.","ops":[{"e":["Clinic","Station"],"state":"from-b"},{"v":"Clinic","state":"waiting"},{"panel":"queue-a","list":[{"key":"Market","note":"2"},{"key":"Bakery","note":"4"}]},{"panel":"queue-b","list":[{"key":"Clinic","note":"2"},{"key":"Park","note":"6"}]},{"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":"8"}},{"panel":"numbers","set":{"Dijkstra settles":"8"}}]},{"say":"Library to Station leads into Station, so the search from the goal takes it backward: 0 + 5 = 5.","ops":[{"e":["Library","Station"],"state":"from-b"},{"v":"Library","state":"waiting"},{"panel":"queue-a","list":[{"key":"Market","note":"2"},{"key":"Bakery","note":"4"}]},{"panel":"queue-b","list":[{"key":"Clinic","note":"2"},{"key":"Library","note":"5"},{"key":"Park","note":"6"}]},{"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":"8"}},{"panel":"numbers","set":{"Dijkstra settles":"8"}}]},{"say":"The next times are 2 from the start and 2 from the goal: 2 + 2 = 4, and no route is known yet, so go on. Settle Market from the start at 2.","ops":[{"v":"Market","state":"settled-a"},{"panel":"queue-a","list":[{"key":"Bakery","note":"4"}]},{"panel":"queue-b","list":[{"key":"Clinic","note":"2"},{"key":"Library","note":"5"},{"key":"Park","note":"6"}]},{"panel":"numbers","set":{"Settled from the start":"2"}},{"panel":"numbers","set":{"Settled from the goal":"1"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"8"}},{"panel":"numbers","set":{"Dijkstra settles":"8"}}]},{"say":"Market to Bakery: 2 + 1 = 3.","ops":[{"e":["Market","Bakery"],"state":"from-a"},{"v":"Bakery","state":"waiting"},{"e":["Depot","Bakery"],"state":"examined"},{"panel":"queue-a","list":[{"key":"Bakery","note":"3"}]},{"panel":"queue-b","list":[{"key":"Clinic","note":"2"},{"key":"Library","note":"5"},{"key":"Park","note":"6"}]},{"panel":"numbers","set":{"Settled from the start":"2"}},{"panel":"numbers","set":{"Settled from the goal":"1"}},{"panel":"numbers","set":{"Best route so far":"–"}},{"panel":"numbers","set":{"A* settles":"8"}},{"panel":"numbers","set":{"Dijkstra settles":"8"}}]},{"say":"Market to Park: 2 + 8 = 10. The other side has reached Park at 6, so a route goes through it: 10 + 6 = 16, the best so far.","ops":[{"e":["Market","Park"],"state":"from-a"},{"v":"Park","state":"waiting"},{"panel":"queue-a","list":[{"key":"Bakery","note":"3"},{"key":"Park","note":"10"}]},{"panel":"queue-b","list":[{"key":"Clinic","note":"2"},{"key":"Library","note":"5"},{"key":"Park","note":"6"}]},{"panel":"numbers","set":{"Settled from the start":"2"}},{"panel":"numbers","set":{"Settled from the goal":"1"}},{"panel":"numbers","set":{"Best route so far":"16 min, through Park"}},{"panel":"numbers","set":{"A* settles":"8"}},{"panel":"numbers","set":{"Dijkstra settles":"8"}}]},{"say":"Market to Clinic: 2 + 10 = 12. The other side has reached Clinic at 2, so a route goes through it: 12 + 2 = 14, the best so far.","ops":[{"e":["Market","Clinic"],"state":"from-a"},{"v":"Clinic","state":"waiting"},{"panel":"queue-a","list":[{"key":"Bakery","note":"3"},{"key":"Park","note":"10"},{"key":"Clinic","note":"12"}]},{"panel":"queue-b","list":[{"key":"Clinic","note":"2"},{"key":"Library","note":"5"},{"key":"Park","note":"6"}]},{"panel":"numbers","set":{"Settled from the start":"2"}},{"panel":"numbers","set":{"Settled from the goal":"1"}},{"panel":"numbers","set":{"Best route so far":"14 min, through Clinic"}},{"panel":"numbers","set":{"A* settles":"8"}},{"panel":"numbers","set":{"Dijkstra settles":"8"}}]},{"say":"The next times are 3 from the start and 2 from the goal: 3 + 2 = 5, less than the best route, 14, so a quicker one may still pass through a vertex in a queue. Go on. Settle Clinic from the goal at 2.","ops":[{"v":"Clinic","state":"settled-b"},{"panel":"queue-a","list":[{"key":"Bakery","note":"3"},{"key":"Park","note":"10"},{"key":"Clinic","note":"12"}]},{"panel":"queue-b","list":[{"key":"Library","note":"5"},{"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":"14 min, through Clinic"}},{"panel":"numbers","set":{"A* settles":"8"}},{"panel":"numbers","set":{"Dijkstra settles":"8"}}]},{"say":"Market to Clinic leads into Clinic, so the search from the goal takes it backward: 2 + 10 = 12. The other side has reached Market at 2 too, but 12 + 2 = 14 is no quicker than 14.","ops":[{"e":["Market","Clinic"],"state":"from-b"},{"panel":"queue-a","list":[{"key":"Bakery","note":"3"},{"key":"Park","note":"10"},{"key":"Clinic","note":"12"}]},{"panel":"queue-b","list":[{"key":"Library","note":"5"},{"key":"Park","note":"6"},{"key":"Market","note":"12"}]},{"panel":"numbers","set":{"Settled from the start":"2"}},{"panel":"numbers","set":{"Settled from the goal":"2"}},{"panel":"numbers","set":{"Best route so far":"14 min, through Clinic"}},{"panel":"numbers","set":{"A* settles":"8"}},{"panel":"numbers","set":{"Dijkstra settles":"8"}}]},{"say":"The next times are 3 from the start and 5 from the goal: 3 + 5 = 8, less than the best route, 14, so a quicker one may still pass through a vertex in a queue. Go on. Settle Bakery from the start at 3.","ops":[{"v":"Bakery","state":"settled-a"},{"panel":"queue-a","list":[{"key":"Park","note":"10"},{"key":"Clinic","note":"12"}]},{"panel":"queue-b","list":[{"key":"Library","note":"5"},{"key":"Park","note":"6"},{"key":"Market","note":"12"}]},{"panel":"numbers","set":{"Settled from the start":"3"}},{"panel":"numbers","set":{"Settled from the goal":"2"}},{"panel":"numbers","set":{"Best route so far":"14 min, through Clinic"}},{"panel":"numbers","set":{"A* settles":"8"}},{"panel":"numbers","set":{"Dijkstra settles":"8"}}]},{"say":"Bakery to School: 3 + 5 = 8.","ops":[{"e":["Bakery","School"],"state":"from-a"},{"v":"School","state":"waiting"},{"panel":"queue-a","list":[{"key":"School","note":"8"},{"key":"Park","note":"10"},{"key":"Clinic","note":"12"}]},{"panel":"queue-b","list":[{"key":"Library","note":"5"},{"key":"Park","note":"6"},{"key":"Market","note":"12"}]},{"panel":"numbers","set":{"Settled from the start":"3"}},{"panel":"numbers","set":{"Settled from the goal":"2"}},{"panel":"numbers","set":{"Best route so far":"14 min, through Clinic"}},{"panel":"numbers","set":{"A* settles":"8"}},{"panel":"numbers","set":{"Dijkstra settles":"8"}}]},{"say":"Bakery to Park: 3 + 7 = 10, not quicker than 10.","ops":[{"e":["Bakery","Park"],"state":"examined"}]},{"say":"The next times are 8 from the start and 5 from the goal: 8 + 5 = 13, less than the best route, 14, so a quicker one may still pass through a vertex in a queue. Go on. Settle Library from the goal at 5.","ops":[{"v":"Library","state":"settled-b"},{"panel":"queue-a","list":[{"key":"School","note":"8"},{"key":"Park","note":"10"},{"key":"Clinic","note":"12"}]},{"panel":"queue-b","list":[{"key":"Park","note":"6"},{"key":"Market","note":"12"}]},{"panel":"numbers","set":{"Settled from the start":"3"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"14 min, through Clinic"}},{"panel":"numbers","set":{"A* settles":"8"}},{"panel":"numbers","set":{"Dijkstra settles":"8"}}]},{"say":"School to Library leads into Library, so the search from the goal takes it backward: 5 + 3 = 8. The other side has reached School at 8 too, but 8 + 8 = 16 is no quicker than 14.","ops":[{"e":["School","Library"],"state":"from-b"},{"v":"School","state":"waiting"},{"panel":"queue-a","list":[{"key":"School","note":"8"},{"key":"Park","note":"10"},{"key":"Clinic","note":"12"}]},{"panel":"queue-b","list":[{"key":"Park","note":"6"},{"key":"School","note":"8"},{"key":"Market","note":"12"}]},{"panel":"numbers","set":{"Settled from the start":"3"}},{"panel":"numbers","set":{"Settled from the goal":"3"}},{"panel":"numbers","set":{"Best route so far":"14 min, through Clinic"}},{"panel":"numbers","set":{"A* settles":"8"}},{"panel":"numbers","set":{"Dijkstra settles":"8"}}]},{"say":"Park to Library leads into Library, so the search from the goal takes it backward: 5 + 2 = 7, not quicker than 6.","ops":[{"e":["Park","Library"],"state":"examined"}]},{"say":"Stop: the next times, 8 from the start and 6 from the goal, add up to 14, no less than the best route, 14, so no route left to find can be quicker. The quickest route meets at Clinic and takes 14 minutes. The searches settled 3 vertices from the start and 3 from the goal.","ops":[{"e":["Depot","Market"],"state":"tree"},{"e":["Market","Clinic"],"state":"tree"},{"e":["Clinic","Station"],"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, \"Depot\", \"Station\", 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}"}
