{"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":"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, and which places does the search look at on the way?","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. path.DijkstraPaths finds the same time by settling all 6 vertices Home 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 Home, which is 0. The guess of the time left is the straight-line distance to School at the fastest any street on the drawing goes between its two ends, so it never says more than the true time. From Home it is 4.9492 minutes, so Home goes in the queue at 0 + 4.9492 = 4.9492.","ops":[{"v":"Home","state":"waiting"},{"panel":"queue","list":[{"key":"Home","note":"4.9492"}]},{"panel":"dist","set":{"Home":"0"}},{"panel":"dist","set":{"Bakery":"∞"}},{"panel":"dist","set":{"Bridge":"∞"}},{"panel":"dist","set":{"Park":"∞"}},{"panel":"dist","set":{"Library":"∞"}},{"panel":"dist","set":{"School":"∞"}},{"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":"6"}}]},{"say":"Take Home from the queue: 0 minutes so far plus a guess of 4.9492 to go makes 4.9492, the lowest in the queue.","ops":[{"v":"Home","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":"4.9492 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"6"}}]},{"say":"Home to Bakery: 0 + 4 = 4. The guess from Bakery is 3.8918, so Bakery goes in the queue at 4 + 3.8918 = 7.8918.","ops":[{"v":"Bakery","state":"waiting"},{"e":["Home","Bakery"],"state":"tree"},{"panel":"dist","set":{"Bakery":"4"}},{"panel":"queue","list":[{"key":"Bakery","note":"7.8918"}]},{"panel":"numbers","set":{"Settled":"1"}},{"panel":"numbers","set":{"In queue":"1"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"4.9492 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"6"}}]},{"say":"Home to Bridge: 0 + 3 = 3. The guess from Bridge is 3.3986, so Bridge goes in the queue at 3 + 3.3986 = 6.3986.","ops":[{"v":"Bridge","state":"waiting"},{"e":["Home","Bridge"],"state":"tree"},{"panel":"dist","set":{"Bridge":"3"}},{"panel":"queue","list":[{"key":"Bridge","note":"6.3986"},{"key":"Bakery","note":"7.8918"}]},{"panel":"numbers","set":{"Settled":"1"}},{"panel":"numbers","set":{"In queue":"2"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"4.9492 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"6"}}]},{"say":"Take Bridge from the queue: 3 minutes so far plus a guess of 3.3986 to go makes 6.3986, the lowest in the queue.","ops":[{"v":"Bridge","state":"current"},{"panel":"queue","list":[{"key":"Bakery","note":"7.8918"}]},{"v":"Home","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":"3.3986 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"6"}}]},{"say":"Bridge to Park: 3 + 2 = 5. The guess from Park is 1.8962, so Park goes in the queue at 5 + 1.8962 = 6.8962.","ops":[{"v":"Park","state":"waiting"},{"e":["Bridge","Park"],"state":"tree"},{"panel":"dist","set":{"Park":"5"}},{"panel":"queue","list":[{"key":"Park","note":"6.8962"},{"key":"Bakery","note":"7.8918"}]},{"panel":"numbers","set":{"Settled":"2"}},{"panel":"numbers","set":{"In queue":"2"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"3.3986 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"6"}}]},{"say":"Take Park from the queue: 5 minutes so far plus a guess of 1.8962 to go makes 6.8962, the lowest in the queue.","ops":[{"v":"Park","state":"current"},{"panel":"queue","list":[{"key":"Bakery","note":"7.8918"}]},{"v":"Bridge","state":"done"},{"panel":"numbers","set":{"Settled":"3"}},{"panel":"numbers","set":{"In queue":"1"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"1.8962 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"6"}}]},{"say":"Park to Bakery: 5 + 3 = 8, not quicker than 4, so Bakery stays in the queue at 7.8918.","ops":[{"e":["Park","Bakery"],"state":"examined"}]},{"say":"Park to Library: 5 + 4 = 9. The guess from Library is 1.9197, so Library goes in the queue at 9 + 1.9197 = 10.9197.","ops":[{"v":"Library","state":"waiting"},{"e":["Park","Library"],"state":"tree"},{"panel":"dist","set":{"Library":"9"}},{"panel":"queue","list":[{"key":"Bakery","note":"7.8918"},{"key":"Library","note":"10.9197"}]},{"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.8962 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"6"}}]},{"say":"Park to School: 5 + 7 = 12. The guess from School is 0, so School goes in the queue at 12 + 0 = 12.","ops":[{"v":"School","state":"waiting"},{"e":["Park","School"],"state":"tree"},{"panel":"dist","set":{"School":"12"}},{"panel":"queue","list":[{"key":"Bakery","note":"7.8918"},{"key":"Library","note":"10.9197"},{"key":"School","note":"12"}]},{"panel":"numbers","set":{"Settled":"3"}},{"panel":"numbers","set":{"In queue":"3"}},{"panel":"numbers","set":{"Best time to goal":"12 min"}},{"panel":"numbers","set":{"Guess to goal":"1.8962 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"6"}}]},{"say":"Take Bakery from the queue: 4 minutes so far plus a guess of 3.8918 to go makes 7.8918, the lowest in the queue.","ops":[{"v":"Bakery","state":"current"},{"panel":"queue","list":[{"key":"Library","note":"10.9197"},{"key":"School","note":"12"}]},{"v":"Park","state":"done"},{"panel":"numbers","set":{"Settled":"4"}},{"panel":"numbers","set":{"In queue":"2"}},{"panel":"numbers","set":{"Best time to goal":"12 min"}},{"panel":"numbers","set":{"Guess to goal":"3.8918 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"6"}}]},{"say":"Take Library from the queue: 9 minutes so far plus a guess of 1.9197 to go makes 10.9197, the lowest in the queue.","ops":[{"v":"Library","state":"current"},{"panel":"queue","list":[{"key":"School","note":"12"}]},{"v":"Bakery","state":"done"},{"panel":"numbers","set":{"Settled":"5"}},{"panel":"numbers","set":{"In queue":"1"}},{"panel":"numbers","set":{"Best time to goal":"12 min"}},{"panel":"numbers","set":{"Guess to goal":"1.9197 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"6"}}]},{"say":"Library to School: 9 + 2 = 11, quicker than 12, so School moves up the queue to 11 + 0 = 11.","ops":[{"e":["Park","School"],"state":"examined"},{"e":["Library","School"],"state":"tree"},{"panel":"dist","set":{"School":"11"}},{"panel":"queue","list":[{"key":"School","note":"11"}]},{"panel":"numbers","set":{"Settled":"5"}},{"panel":"numbers","set":{"In queue":"1"}},{"panel":"numbers","set":{"Best time to goal":"11 min"}},{"panel":"numbers","set":{"Guess to goal":"1.9197 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"6"}}]},{"say":"Take School from the queue at 11 minutes. That's the goal, so the quickest route there is known, and A* stops. It settled 6 vertices, where Dijkstra settles 6 by the time it reaches School.","ops":[{"v":"School","state":"current"},{"panel":"queue","list":[]},{"v":"Library","state":"done"},{"panel":"numbers","set":{"Settled":"6"}},{"panel":"numbers","set":{"In queue":"0"}},{"panel":"numbers","set":{"Best time to goal":"11 min"}},{"panel":"numbers","set":{"Guess to goal":"0 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"6"}}]}],"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[\"School\"]\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, \"Home\", \"School\", 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}"}
