{"algorithm":"astar","about":["A* is how a navigation app finds one route from A to B. It runs like Dijkstra, but it orders its queue by the time so far plus a guess of the time left to B. So it always looks first at the vertex that seems to lead to B soonest, and it stops as soon as B leaves the queue. Dijkstra orders by the time so far alone and spreads out in every direction alike.","The guess on this page is the straight-line distance to B divided by the fastest speed on the map: the most distance per minute between its two ends that any street covers. No route can beat a straight line at that speed, so the guess never says more than the true time, and the route A* returns is the quickest. A guess that can say more than the true time can return a slower route. The guess needs each vertex's place, which only works where the vertices have positions, such as on a map.","This guess is also consistent: it never drops by more than the time of the street between two vertices. Then each vertex leaves the queue once, and A* costs O((V+E) log V), less in practice, since it stops at B. gograph calls the guess at most once for each vertex and never for B. With a guess that isn't consistent, it can take a vertex out of the queue again when a quicker way to it turns up.","path.AStar takes the edge cost and the guess as functions. A nil cost uses the edge weight, and a nil guess makes it Dijkstra. A negative cost returns ErrNegativeWeight, and a goal the start can't reach returns ErrUnreachable. Landmarks, the ALT method, give a sharper guess than a straight line on road networks."],"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, and which stops does the search look at to find it?","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. path.DijkstraPaths finds the same time by settling all 8 vertices Depot can reach.","legend":{"vertex":[{"id":"idle","label":"Not reached","color":"#64748B","shape":"hollow"},{"id":"waiting","label":"In queue","color":"#E69F00","shape":"dashed-square"},{"id":"current","label":"Being settled","color":"#56B4E9","shape":"ring"},{"id":"done","label":"Settled","color":"#009E73","shape":"filled"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"tree","label":"Quickest way in so far","color":"#009E73","shape":"thick"},{"id":"examined","label":"Checked, not quicker","color":"#CC79A7","shape":"dashed"}],"panels":[{"id":"queue","title":"Queue, by time so far plus guess","kind":"list"},{"id":"dist","title":"Minutes so far","kind":"table"},{"id":"numbers","title":"So far","kind":"numbers"}]},"steps":[{"say":"Every time starts at ∞, except Depot, which is 0. The guess of the time left is the straight-line distance to Station at the fastest any street on the drawing goes between its two ends, so it never says more than the true time. From Depot it is 1.9614 minutes, so Depot goes in the queue at 0 + 1.9614 = 1.9614.","ops":[{"v":"Depot","state":"waiting"},{"panel":"queue","list":[{"key":"Depot","note":"1.9614"}]},{"panel":"dist","set":{"Depot":"0"}},{"panel":"dist","set":{"Bakery":"∞"}},{"panel":"dist","set":{"Market":"∞"}},{"panel":"dist","set":{"School":"∞"}},{"panel":"dist","set":{"Park":"∞"}},{"panel":"dist","set":{"Clinic":"∞"}},{"panel":"dist","set":{"Library":"∞"}},{"panel":"dist","set":{"Station":"∞"}},{"panel":"numbers","set":{"Settled":"0"}},{"panel":"numbers","set":{"In queue":"1"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"–"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"8"}}]},{"say":"Take Depot from the queue: 0 minutes so far plus a guess of 1.9614 to go makes 1.9614, the lowest in the queue.","ops":[{"v":"Depot","state":"current"},{"panel":"queue","list":[]},{"panel":"numbers","set":{"Settled":"1"}},{"panel":"numbers","set":{"In queue":"0"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"1.9614 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"8"}}]},{"say":"Depot to Bakery: 0 + 4 = 4. The guess from Bakery is 1.618, so Bakery goes in the queue at 4 + 1.618 = 5.618.","ops":[{"v":"Bakery","state":"waiting"},{"e":["Depot","Bakery"],"state":"tree"},{"panel":"dist","set":{"Bakery":"4"}},{"panel":"queue","list":[{"key":"Bakery","note":"5.618"}]},{"panel":"numbers","set":{"Settled":"1"}},{"panel":"numbers","set":{"In queue":"1"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"1.9614 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"8"}}]},{"say":"Depot to Market: 0 + 2 = 2. The guess from Market is 1.3359, so Market goes in the queue at 2 + 1.3359 = 3.3359.","ops":[{"v":"Market","state":"waiting"},{"e":["Depot","Market"],"state":"tree"},{"panel":"dist","set":{"Market":"2"}},{"panel":"queue","list":[{"key":"Market","note":"3.3359"},{"key":"Bakery","note":"5.618"}]},{"panel":"numbers","set":{"Settled":"1"}},{"panel":"numbers","set":{"In queue":"2"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"1.9614 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"8"}}]},{"say":"Take Market from the queue: 2 minutes so far plus a guess of 1.3359 to go makes 3.3359, the lowest in the queue.","ops":[{"v":"Market","state":"current"},{"panel":"queue","list":[{"key":"Bakery","note":"5.618"}]},{"v":"Depot","state":"done"},{"panel":"numbers","set":{"Settled":"2"}},{"panel":"numbers","set":{"In queue":"1"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"1.3359 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"8"}}]},{"say":"Market to Bakery: 2 + 1 = 3, quicker than 4, so Bakery moves up the queue to 3 + 1.618 = 4.618.","ops":[{"e":["Depot","Bakery"],"state":"examined"},{"e":["Market","Bakery"],"state":"tree"},{"panel":"dist","set":{"Bakery":"3"}},{"panel":"queue","list":[{"key":"Bakery","note":"4.618"}]},{"panel":"numbers","set":{"Settled":"2"}},{"panel":"numbers","set":{"In queue":"1"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"1.3359 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"8"}}]},{"say":"Market to Park: 2 + 8 = 10. The guess from Park is 0.7454, so Park goes in the queue at 10 + 0.7454 = 10.7454.","ops":[{"v":"Park","state":"waiting"},{"e":["Market","Park"],"state":"tree"},{"panel":"dist","set":{"Park":"10"}},{"panel":"queue","list":[{"key":"Bakery","note":"4.618"},{"key":"Park","note":"10.7454"}]},{"panel":"numbers","set":{"Settled":"2"}},{"panel":"numbers","set":{"In queue":"2"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"1.3359 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"8"}}]},{"say":"Market to Clinic: 2 + 10 = 12. The guess from Clinic is 0.6872, so Clinic goes in the queue at 12 + 0.6872 = 12.6872.","ops":[{"v":"Clinic","state":"waiting"},{"e":["Market","Clinic"],"state":"tree"},{"panel":"dist","set":{"Clinic":"12"}},{"panel":"queue","list":[{"key":"Bakery","note":"4.618"},{"key":"Park","note":"10.7454"},{"key":"Clinic","note":"12.6872"}]},{"panel":"numbers","set":{"Settled":"2"}},{"panel":"numbers","set":{"In queue":"3"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"1.3359 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"8"}}]},{"say":"Take Bakery from the queue: 3 minutes so far plus a guess of 1.618 to go makes 4.618, the lowest in the queue.","ops":[{"v":"Bakery","state":"current"},{"panel":"queue","list":[{"key":"Park","note":"10.7454"},{"key":"Clinic","note":"12.6872"}]},{"v":"Market","state":"done"},{"panel":"numbers","set":{"Settled":"3"}},{"panel":"numbers","set":{"In queue":"2"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"1.618 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"8"}}]},{"say":"Bakery to School: 3 + 5 = 8. The guess from School is 1.1335, so School goes in the queue at 8 + 1.1335 = 9.1335.","ops":[{"v":"School","state":"waiting"},{"e":["Bakery","School"],"state":"tree"},{"panel":"dist","set":{"School":"8"}},{"panel":"queue","list":[{"key":"School","note":"9.1335"},{"key":"Park","note":"10.7454"},{"key":"Clinic","note":"12.6872"}]},{"panel":"numbers","set":{"Settled":"3"}},{"panel":"numbers","set":{"In queue":"3"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"1.618 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"8"}}]},{"say":"Bakery to Park: 3 + 7 = 10, not quicker than 10, so Park stays in the queue at 10.7454.","ops":[{"e":["Bakery","Park"],"state":"examined"}]},{"say":"Take School from the queue: 8 minutes so far plus a guess of 1.1335 to go makes 9.1335, the lowest in the queue.","ops":[{"v":"School","state":"current"},{"panel":"queue","list":[{"key":"Park","note":"10.7454"},{"key":"Clinic","note":"12.6872"}]},{"v":"Bakery","state":"done"},{"panel":"numbers","set":{"Settled":"4"}},{"panel":"numbers","set":{"In queue":"2"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"1.1335 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"8"}}]},{"say":"School to Library: 8 + 3 = 11. The guess from Library is 0.6719, so Library goes in the queue at 11 + 0.6719 = 11.6719.","ops":[{"v":"Library","state":"waiting"},{"e":["School","Library"],"state":"tree"},{"panel":"dist","set":{"Library":"11"}},{"panel":"queue","list":[{"key":"Park","note":"10.7454"},{"key":"Library","note":"11.6719"},{"key":"Clinic","note":"12.6872"}]},{"panel":"numbers","set":{"Settled":"4"}},{"panel":"numbers","set":{"In queue":"3"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"1.1335 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"8"}}]},{"say":"Take Park from the queue: 10 minutes so far plus a guess of 0.7454 to go makes 10.7454, the lowest in the queue.","ops":[{"v":"Park","state":"current"},{"panel":"queue","list":[{"key":"Library","note":"11.6719"},{"key":"Clinic","note":"12.6872"}]},{"v":"School","state":"done"},{"panel":"numbers","set":{"Settled":"5"}},{"panel":"numbers","set":{"In queue":"2"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"0.7454 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"8"}}]},{"say":"Park to Library: 10 + 2 = 12, not quicker than 11, so Library stays in the queue at 11.6719.","ops":[{"e":["Park","Library"],"state":"examined"}]},{"say":"Park to Station: 10 + 6 = 16. The guess from Station is 0, so Station goes in the queue at 16 + 0 = 16.","ops":[{"v":"Station","state":"waiting"},{"e":["Park","Station"],"state":"tree"},{"panel":"dist","set":{"Station":"16"}},{"panel":"queue","list":[{"key":"Library","note":"11.6719"},{"key":"Clinic","note":"12.6872"},{"key":"Station","note":"16"}]},{"panel":"numbers","set":{"Settled":"5"}},{"panel":"numbers","set":{"In queue":"3"}},{"panel":"numbers","set":{"Best time to goal":"16 min"}},{"panel":"numbers","set":{"Guess to goal":"0.7454 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"8"}}]},{"say":"Take Library from the queue: 11 minutes so far plus a guess of 0.6719 to go makes 11.6719, the lowest in the queue.","ops":[{"v":"Library","state":"current"},{"panel":"queue","list":[{"key":"Clinic","note":"12.6872"},{"key":"Station","note":"16"}]},{"v":"Park","state":"done"},{"panel":"numbers","set":{"Settled":"6"}},{"panel":"numbers","set":{"In queue":"2"}},{"panel":"numbers","set":{"Best time to goal":"16 min"}},{"panel":"numbers","set":{"Guess to goal":"0.6719 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"8"}}]},{"say":"Library to Station: 11 + 5 = 16, not quicker than 16, so Station stays in the queue at 16.","ops":[{"e":["Library","Station"],"state":"examined"}]},{"say":"Take Clinic from the queue: 12 minutes so far plus a guess of 0.6872 to go makes 12.6872, the lowest in the queue.","ops":[{"v":"Clinic","state":"current"},{"panel":"queue","list":[{"key":"Station","note":"16"}]},{"v":"Library","state":"done"},{"panel":"numbers","set":{"Settled":"7"}},{"panel":"numbers","set":{"In queue":"1"}},{"panel":"numbers","set":{"Best time to goal":"16 min"}},{"panel":"numbers","set":{"Guess to goal":"0.6872 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"8"}}]},{"say":"Clinic to Station: 12 + 2 = 14, quicker than 16, so Station moves up the queue to 14 + 0 = 14.","ops":[{"e":["Park","Station"],"state":"examined"},{"e":["Clinic","Station"],"state":"tree"},{"panel":"dist","set":{"Station":"14"}},{"panel":"queue","list":[{"key":"Station","note":"14"}]},{"panel":"numbers","set":{"Settled":"7"}},{"panel":"numbers","set":{"In queue":"1"}},{"panel":"numbers","set":{"Best time to goal":"14 min"}},{"panel":"numbers","set":{"Guess to goal":"0.6872 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"8"}}]},{"say":"Take Station from the queue at 14 minutes. That's the goal, so the quickest route there is known, and A* stops. It settled 8 vertices, where Dijkstra settles 8 by the time it reaches Station.","ops":[{"v":"Station","state":"current"},{"panel":"queue","list":[]},{"v":"Clinic","state":"done"},{"panel":"numbers","set":{"Settled":"8"}},{"panel":"numbers","set":{"In queue":"0"}},{"panel":"numbers","set":{"Best time to goal":"14 min"}},{"panel":"numbers","set":{"Guess to goal":"0 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"8"}}]}],"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":"goal := where[\"Station\"]\nguess := func(v string) float64 {\n\tp := where[v]\n\treturn math.Hypot(p[0]-goal[0], p[1]-goal[1]) / speed\n}\n\nroute, minutes, err := path.AStar(g, \"Depot\", \"Station\", nil, guess)\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}"}
