{"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":"downtown-grid","name":"Downtown grid","description":"Twenty intersections on a downtown street grid. Streets go both ways, Market is closed to cars between 2nd and 3rd, and each edge is the travel time in minutes.","family":"road","directed":true,"weighted":true,"acyclic":false,"vertices":[{"id":"Pine & 1st","x":76,"y":156},{"id":"Pine & 2nd","x":283,"y":188},{"id":"Pine & 3rd","x":496,"y":189},{"id":"Pine & 4th","x":706,"y":160},{"id":"Pine & 5th","x":931,"y":161},{"id":"Main & 1st","x":68,"y":383},{"id":"Main & 2nd","x":268,"y":404},{"id":"Main & 3rd","x":518,"y":374},{"id":"Main & 4th","x":739,"y":393},{"id":"Main & 5th","x":946,"y":381},{"id":"Market & 1st","x":73,"y":597},{"id":"Market & 2nd","x":276,"y":620},{"id":"Market & 3rd","x":512,"y":609},{"id":"Market & 4th","x":704,"y":593},{"id":"Market & 5th","x":958,"y":591},{"id":"River & 1st","x":53,"y":842},{"id":"River & 2nd","x":274,"y":833},{"id":"River & 3rd","x":489,"y":826},{"id":"River & 4th","x":701,"y":833},{"id":"River & 5th","x":950,"y":829}],"edges":[{"from":"Pine & 1st","to":"Pine & 2nd","weight":2},{"from":"Pine & 2nd","to":"Pine & 1st","weight":2},{"from":"Pine & 1st","to":"Main & 1st","weight":2},{"from":"Main & 1st","to":"Pine & 1st","weight":2},{"from":"Pine & 2nd","to":"Pine & 3rd","weight":3},{"from":"Pine & 3rd","to":"Pine & 2nd","weight":3},{"from":"Pine & 2nd","to":"Main & 2nd","weight":3},{"from":"Main & 2nd","to":"Pine & 2nd","weight":3},{"from":"Pine & 3rd","to":"Pine & 4th","weight":2},{"from":"Pine & 4th","to":"Pine & 3rd","weight":2},{"from":"Pine & 3rd","to":"Main & 3rd","weight":2},{"from":"Main & 3rd","to":"Pine & 3rd","weight":2},{"from":"Pine & 4th","to":"Pine & 5th","weight":3},{"from":"Pine & 5th","to":"Pine & 4th","weight":3},{"from":"Pine & 4th","to":"Main & 4th","weight":2},{"from":"Main & 4th","to":"Pine & 4th","weight":2},{"from":"Pine & 5th","to":"Main & 5th","weight":3},{"from":"Main & 5th","to":"Pine & 5th","weight":3},{"from":"Main & 1st","to":"Main & 2nd","weight":3},{"from":"Main & 2nd","to":"Main & 1st","weight":3},{"from":"Main & 1st","to":"Market & 1st","weight":3},{"from":"Market & 1st","to":"Main & 1st","weight":3},{"from":"Main & 2nd","to":"Main & 3rd","weight":4},{"from":"Main & 3rd","to":"Main & 2nd","weight":4},{"from":"Main & 2nd","to":"Market & 2nd","weight":2},{"from":"Market & 2nd","to":"Main & 2nd","weight":2},{"from":"Main & 3rd","to":"Main & 4th","weight":4},{"from":"Main & 4th","to":"Main & 3rd","weight":4},{"from":"Main & 3rd","to":"Market & 3rd","weight":3},{"from":"Market & 3rd","to":"Main & 3rd","weight":3},{"from":"Main & 4th","to":"Main & 5th","weight":3},{"from":"Main & 5th","to":"Main & 4th","weight":3},{"from":"Main & 4th","to":"Market & 4th","weight":2},{"from":"Market & 4th","to":"Main & 4th","weight":2},{"from":"Main & 5th","to":"Market & 5th","weight":2},{"from":"Market & 5th","to":"Main & 5th","weight":2},{"from":"Market & 1st","to":"Market & 2nd","weight":2},{"from":"Market & 2nd","to":"Market & 1st","weight":2},{"from":"Market & 1st","to":"River & 1st","weight":2},{"from":"River & 1st","to":"Market & 1st","weight":2},{"from":"Market & 2nd","to":"River & 2nd","weight":2},{"from":"River & 2nd","to":"Market & 2nd","weight":2},{"from":"Market & 3rd","to":"Market & 4th","weight":3},{"from":"Market & 4th","to":"Market & 3rd","weight":3},{"from":"Market & 3rd","to":"River & 3rd","weight":3},{"from":"River & 3rd","to":"Market & 3rd","weight":3},{"from":"Market & 4th","to":"Market & 5th","weight":2},{"from":"Market & 5th","to":"Market & 4th","weight":2},{"from":"Market & 4th","to":"River & 4th","weight":3},{"from":"River & 4th","to":"Market & 4th","weight":3},{"from":"Market & 5th","to":"River & 5th","weight":2},{"from":"River & 5th","to":"Market & 5th","weight":2},{"from":"River & 1st","to":"River & 2nd","weight":3},{"from":"River & 2nd","to":"River & 1st","weight":3},{"from":"River & 2nd","to":"River & 3rd","weight":2},{"from":"River & 3rd","to":"River & 2nd","weight":2},{"from":"River & 3rd","to":"River & 4th","weight":2},{"from":"River & 4th","to":"River & 3rd","weight":2},{"from":"River & 4th","to":"River & 5th","weight":4},{"from":"River & 5th","to":"River & 4th","weight":4}],"details":{"vertices":20,"edges":60,"directed":true,"weighted":true,"acyclic":false,"weightMin":2,"weightMax":4,"negativeWeights":false,"density":0.15789473684210525,"inDegree":{"min":2,"avg":3,"max":4},"outDegree":{"min":2,"avg":3,"max":4},"selfLoops":0,"components":1}},"problem":"What is the quickest drive from Pine & 1st to River & 5th, with Market closed between 2nd and 3rd, and how many intersections does the search look at?","params":{"start":"Pine & 1st","goal":"River & 5th"},"result":{"kind":"route","vertices":["Pine \u0026 1st","Pine \u0026 2nd","Pine \u0026 3rd","Pine \u0026 4th","Main \u0026 4th","Market \u0026 4th","Market \u0026 5th","River \u0026 5th"],"cost":15},"answer":"The quickest drive from Pine & 1st to River & 5th takes 15 minutes, along 7 streets. path.DijkstraPaths finds the same time by settling all 20 vertices Pine & 1st 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 Pine & 1st, which is 0. The guess of the time left is the straight-line distance to River & 5th at the fastest any street on the drawing goes between its two ends, so it never says more than the true time. From Pine & 1st it is 8.6855 minutes, so Pine & 1st goes in the queue at 0 + 8.6855 = 8.6855.","ops":[{"v":"Pine & 1st","state":"waiting"},{"panel":"queue","list":[{"key":"Pine & 1st","note":"8.6855"}]},{"panel":"dist","set":{"Pine & 1st":"0"}},{"panel":"dist","set":{"Pine & 2nd":"∞"}},{"panel":"dist","set":{"Pine & 3rd":"∞"}},{"panel":"dist","set":{"Pine & 4th":"∞"}},{"panel":"dist","set":{"Pine & 5th":"∞"}},{"panel":"dist","set":{"Main & 1st":"∞"}},{"panel":"dist","set":{"Main & 2nd":"∞"}},{"panel":"dist","set":{"Main & 3rd":"∞"}},{"panel":"dist","set":{"Main & 4th":"∞"}},{"panel":"dist","set":{"Main & 5th":"∞"}},{"panel":"dist","set":{"Market & 1st":"∞"}},{"panel":"dist","set":{"Market & 2nd":"∞"}},{"panel":"dist","set":{"Market & 3rd":"∞"}},{"panel":"dist","set":{"Market & 4th":"∞"}},{"panel":"dist","set":{"Market & 5th":"∞"}},{"panel":"dist","set":{"River & 1st":"∞"}},{"panel":"dist","set":{"River & 2nd":"∞"}},{"panel":"dist","set":{"River & 3rd":"∞"}},{"panel":"dist","set":{"River & 4th":"∞"}},{"panel":"dist","set":{"River & 5th":"∞"}},{"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":"20"}}]},{"say":"Take Pine & 1st from the queue: 0 minutes so far plus a guess of 8.6855 to go makes 8.6855, the lowest in the queue.","ops":[{"v":"Pine & 1st","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":"8.6855 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Pine & 1st to Pine & 2nd: 0 + 2 = 2. The guess from Pine & 2nd is 7.2839, so Pine & 2nd goes in the queue at 2 + 7.2839 = 9.2839.","ops":[{"v":"Pine & 2nd","state":"waiting"},{"e":["Pine & 1st","Pine & 2nd"],"state":"tree"},{"panel":"dist","set":{"Pine & 2nd":"2"}},{"panel":"queue","list":[{"key":"Pine & 2nd","note":"9.2839"}]},{"panel":"numbers","set":{"Settled":"1"}},{"panel":"numbers","set":{"In queue":"1"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"8.6855 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Pine & 1st to Main & 1st: 0 + 2 = 2. The guess from Main & 1st is 7.7821, so Main & 1st goes in the queue at 2 + 7.7821 = 9.7821.","ops":[{"v":"Main & 1st","state":"waiting"},{"e":["Pine & 1st","Main & 1st"],"state":"tree"},{"panel":"dist","set":{"Main & 1st":"2"}},{"panel":"queue","list":[{"key":"Pine & 2nd","note":"9.2839"},{"key":"Main & 1st","note":"9.7821"}]},{"panel":"numbers","set":{"Settled":"1"}},{"panel":"numbers","set":{"In queue":"2"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"8.6855 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Take Pine & 2nd from the queue: 2 minutes so far plus a guess of 7.2839 to go makes 9.2839, the lowest in the queue.","ops":[{"v":"Pine & 2nd","state":"current"},{"panel":"queue","list":[{"key":"Main & 1st","note":"9.7821"}]},{"v":"Pine & 1st","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":"7.2839 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Pine & 2nd to Pine & 3rd: 2 + 3 = 5. The guess from Pine & 3rd is 6.1784, so Pine & 3rd goes in the queue at 5 + 6.1784 = 11.1784.","ops":[{"v":"Pine & 3rd","state":"waiting"},{"e":["Pine & 2nd","Pine & 3rd"],"state":"tree"},{"panel":"dist","set":{"Pine & 3rd":"5"}},{"panel":"queue","list":[{"key":"Main & 1st","note":"9.7821"},{"key":"Pine & 3rd","note":"11.1784"}]},{"panel":"numbers","set":{"Settled":"2"}},{"panel":"numbers","set":{"In queue":"2"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"7.2839 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Pine & 2nd to Main & 2nd: 2 + 3 = 5. The guess from Main & 2nd is 6.3272, so Main & 2nd goes in the queue at 5 + 6.3272 = 11.3272.","ops":[{"v":"Main & 2nd","state":"waiting"},{"e":["Pine & 2nd","Main & 2nd"],"state":"tree"},{"panel":"dist","set":{"Main & 2nd":"5"}},{"panel":"queue","list":[{"key":"Main & 1st","note":"9.7821"},{"key":"Pine & 3rd","note":"11.1784"},{"key":"Main & 2nd","note":"11.3272"}]},{"panel":"numbers","set":{"Settled":"2"}},{"panel":"numbers","set":{"In queue":"3"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"7.2839 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Take Main & 1st from the queue: 2 minutes so far plus a guess of 7.7821 to go makes 9.7821, the lowest in the queue.","ops":[{"v":"Main & 1st","state":"current"},{"panel":"queue","list":[{"key":"Pine & 3rd","note":"11.1784"},{"key":"Main & 2nd","note":"11.3272"}]},{"v":"Pine & 2nd","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":"7.7821 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Main & 1st to Main & 2nd: 2 + 3 = 5, not quicker than 5, so Main & 2nd stays in the queue at 11.3272.","ops":[{"e":["Main & 1st","Main & 2nd"],"state":"examined"}]},{"say":"Main & 1st to Market & 1st: 2 + 3 = 5. The guess from Market & 1st is 7.1428, so Market & 1st goes in the queue at 5 + 7.1428 = 12.1428.","ops":[{"v":"Market & 1st","state":"waiting"},{"e":["Main & 1st","Market & 1st"],"state":"tree"},{"panel":"dist","set":{"Market & 1st":"5"}},{"panel":"queue","list":[{"key":"Pine & 3rd","note":"11.1784"},{"key":"Main & 2nd","note":"11.3272"},{"key":"Market & 1st","note":"12.1428"}]},{"panel":"numbers","set":{"Settled":"3"}},{"panel":"numbers","set":{"In queue":"3"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"7.7821 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Take Pine & 3rd from the queue: 5 minutes so far plus a guess of 6.1784 to go makes 11.1784, the lowest in the queue.","ops":[{"v":"Pine & 3rd","state":"current"},{"panel":"queue","list":[{"key":"Main & 2nd","note":"11.3272"},{"key":"Market & 1st","note":"12.1428"}]},{"v":"Main & 1st","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":"6.1784 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Pine & 3rd to Pine & 4th: 5 + 2 = 7. The guess from Pine & 4th is 5.607, so Pine & 4th goes in the queue at 7 + 5.607 = 12.607.","ops":[{"v":"Pine & 4th","state":"waiting"},{"e":["Pine & 3rd","Pine & 4th"],"state":"tree"},{"panel":"dist","set":{"Pine & 4th":"7"}},{"panel":"queue","list":[{"key":"Main & 2nd","note":"11.3272"},{"key":"Market & 1st","note":"12.1428"},{"key":"Pine & 4th","note":"12.607"}]},{"panel":"numbers","set":{"Settled":"4"}},{"panel":"numbers","set":{"In queue":"3"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"6.1784 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Pine & 3rd to Main & 3rd: 5 + 2 = 7. The guess from Main & 3rd is 4.9401, so Main & 3rd goes in the queue at 7 + 4.9401 = 11.9401.","ops":[{"v":"Main & 3rd","state":"waiting"},{"e":["Pine & 3rd","Main & 3rd"],"state":"tree"},{"panel":"dist","set":{"Main & 3rd":"7"}},{"panel":"queue","list":[{"key":"Main & 2nd","note":"11.3272"},{"key":"Main & 3rd","note":"11.9401"},{"key":"Market & 1st","note":"12.1428"},{"key":"Pine & 4th","note":"12.607"}]},{"panel":"numbers","set":{"Settled":"4"}},{"panel":"numbers","set":{"In queue":"4"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"6.1784 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Take Main & 2nd from the queue: 5 minutes so far plus a guess of 6.3272 to go makes 11.3272, the lowest in the queue.","ops":[{"v":"Main & 2nd","state":"current"},{"panel":"queue","list":[{"key":"Main & 3rd","note":"11.9401"},{"key":"Market & 1st","note":"12.1428"},{"key":"Pine & 4th","note":"12.607"}]},{"v":"Pine & 3rd","state":"done"},{"panel":"numbers","set":{"Settled":"5"}},{"panel":"numbers","set":{"In queue":"3"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"6.3272 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Main & 2nd to Main & 3rd: 5 + 4 = 9, not quicker than 7, so Main & 3rd stays in the queue at 11.9401.","ops":[{"e":["Main & 2nd","Main & 3rd"],"state":"examined"}]},{"say":"Main & 2nd to Market & 2nd: 5 + 2 = 7. The guess from Market & 2nd is 5.5562, so Market & 2nd goes in the queue at 7 + 5.5562 = 12.5562.","ops":[{"v":"Market & 2nd","state":"waiting"},{"e":["Main & 2nd","Market & 2nd"],"state":"tree"},{"panel":"dist","set":{"Market & 2nd":"7"}},{"panel":"queue","list":[{"key":"Main & 3rd","note":"11.9401"},{"key":"Market & 1st","note":"12.1428"},{"key":"Market & 2nd","note":"12.5562"},{"key":"Pine & 4th","note":"12.607"}]},{"panel":"numbers","set":{"Settled":"5"}},{"panel":"numbers","set":{"In queue":"4"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"6.3272 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Take Main & 3rd from the queue: 7 minutes so far plus a guess of 4.9401 to go makes 11.9401, the lowest in the queue.","ops":[{"v":"Main & 3rd","state":"current"},{"panel":"queue","list":[{"key":"Market & 1st","note":"12.1428"},{"key":"Market & 2nd","note":"12.5562"},{"key":"Pine & 4th","note":"12.607"}]},{"v":"Main & 2nd","state":"done"},{"panel":"numbers","set":{"Settled":"6"}},{"panel":"numbers","set":{"In queue":"3"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"4.9401 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Main & 3rd to Main & 4th: 7 + 4 = 11. The guess from Main & 4th is 3.8138, so Main & 4th goes in the queue at 11 + 3.8138 = 14.8138.","ops":[{"v":"Main & 4th","state":"waiting"},{"e":["Main & 3rd","Main & 4th"],"state":"tree"},{"panel":"dist","set":{"Main & 4th":"11"}},{"panel":"queue","list":[{"key":"Market & 1st","note":"12.1428"},{"key":"Market & 2nd","note":"12.5562"},{"key":"Pine & 4th","note":"12.607"},{"key":"Main & 4th","note":"14.8138"}]},{"panel":"numbers","set":{"Settled":"6"}},{"panel":"numbers","set":{"In queue":"4"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"4.9401 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Main & 3rd to Market & 3rd: 7 + 3 = 10. The guess from Market & 3rd is 3.8593, so Market & 3rd goes in the queue at 10 + 3.8593 = 13.8593.","ops":[{"v":"Market & 3rd","state":"waiting"},{"e":["Main & 3rd","Market & 3rd"],"state":"tree"},{"panel":"dist","set":{"Market & 3rd":"10"}},{"panel":"queue","list":[{"key":"Market & 1st","note":"12.1428"},{"key":"Market & 2nd","note":"12.5562"},{"key":"Pine & 4th","note":"12.607"},{"key":"Market & 3rd","note":"13.8593"},{"key":"Main & 4th","note":"14.8138"}]},{"panel":"numbers","set":{"Settled":"6"}},{"panel":"numbers","set":{"In queue":"5"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"4.9401 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Take Market & 1st from the queue: 5 minutes so far plus a guess of 7.1428 to go makes 12.1428, the lowest in the queue.","ops":[{"v":"Market & 1st","state":"current"},{"panel":"queue","list":[{"key":"Market & 2nd","note":"12.5562"},{"key":"Pine & 4th","note":"12.607"},{"key":"Market & 3rd","note":"13.8593"},{"key":"Main & 4th","note":"14.8138"}]},{"v":"Main & 3rd","state":"done"},{"panel":"numbers","set":{"Settled":"7"}},{"panel":"numbers","set":{"In queue":"4"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"7.1428 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Market & 1st to Market & 2nd: 5 + 2 = 7, not quicker than 7, so Market & 2nd stays in the queue at 12.5562.","ops":[{"e":["Market & 1st","Market & 2nd"],"state":"examined"}]},{"say":"Market & 1st to River & 1st: 5 + 2 = 7. The guess from River & 1st is 7.0635, so River & 1st goes in the queue at 7 + 7.0635 = 14.0635.","ops":[{"v":"River & 1st","state":"waiting"},{"e":["Market & 1st","River & 1st"],"state":"tree"},{"panel":"dist","set":{"River & 1st":"7"}},{"panel":"queue","list":[{"key":"Market & 2nd","note":"12.5562"},{"key":"Pine & 4th","note":"12.607"},{"key":"Market & 3rd","note":"13.8593"},{"key":"River & 1st","note":"14.0635"},{"key":"Main & 4th","note":"14.8138"}]},{"panel":"numbers","set":{"Settled":"7"}},{"panel":"numbers","set":{"In queue":"5"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"7.1428 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Take Market & 2nd from the queue: 7 minutes so far plus a guess of 5.5562 to go makes 12.5562, the lowest in the queue.","ops":[{"v":"Market & 2nd","state":"current"},{"panel":"queue","list":[{"key":"Pine & 4th","note":"12.607"},{"key":"Market & 3rd","note":"13.8593"},{"key":"River & 1st","note":"14.0635"},{"key":"Main & 4th","note":"14.8138"}]},{"v":"Market & 1st","state":"done"},{"panel":"numbers","set":{"Settled":"8"}},{"panel":"numbers","set":{"In queue":"4"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"5.5562 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Market & 2nd to River & 2nd: 7 + 2 = 9. The guess from River & 2nd is 5.3228, so River & 2nd goes in the queue at 9 + 5.3228 = 14.3228.","ops":[{"v":"River & 2nd","state":"waiting"},{"e":["Market & 2nd","River & 2nd"],"state":"tree"},{"panel":"dist","set":{"River & 2nd":"9"}},{"panel":"queue","list":[{"key":"Pine & 4th","note":"12.607"},{"key":"Market & 3rd","note":"13.8593"},{"key":"River & 1st","note":"14.0635"},{"key":"River & 2nd","note":"14.3228"},{"key":"Main & 4th","note":"14.8138"}]},{"panel":"numbers","set":{"Settled":"8"}},{"panel":"numbers","set":{"In queue":"5"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"5.5562 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Take Pine & 4th from the queue: 7 minutes so far plus a guess of 5.607 to go makes 12.607, the lowest in the queue.","ops":[{"v":"Pine & 4th","state":"current"},{"panel":"queue","list":[{"key":"Market & 3rd","note":"13.8593"},{"key":"River & 1st","note":"14.0635"},{"key":"River & 2nd","note":"14.3228"},{"key":"Main & 4th","note":"14.8138"}]},{"v":"Market & 2nd","state":"done"},{"panel":"numbers","set":{"Settled":"9"}},{"panel":"numbers","set":{"In queue":"4"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"5.607 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Pine & 4th to Pine & 5th: 7 + 3 = 10. The guess from Pine & 5th is 5.2618, so Pine & 5th goes in the queue at 10 + 5.2618 = 15.2618.","ops":[{"v":"Pine & 5th","state":"waiting"},{"e":["Pine & 4th","Pine & 5th"],"state":"tree"},{"panel":"dist","set":{"Pine & 5th":"10"}},{"panel":"queue","list":[{"key":"Market & 3rd","note":"13.8593"},{"key":"River & 1st","note":"14.0635"},{"key":"River & 2nd","note":"14.3228"},{"key":"Main & 4th","note":"14.8138"},{"key":"Pine & 5th","note":"15.2618"}]},{"panel":"numbers","set":{"Settled":"9"}},{"panel":"numbers","set":{"In queue":"5"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"5.607 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Pine & 4th to Main & 4th: 7 + 2 = 9, quicker than 11, so Main & 4th moves up the queue to 9 + 3.8138 = 12.8138.","ops":[{"e":["Main & 3rd","Main & 4th"],"state":"examined"},{"e":["Pine & 4th","Main & 4th"],"state":"tree"},{"panel":"dist","set":{"Main & 4th":"9"}},{"panel":"queue","list":[{"key":"Main & 4th","note":"12.8138"},{"key":"Market & 3rd","note":"13.8593"},{"key":"River & 1st","note":"14.0635"},{"key":"River & 2nd","note":"14.3228"},{"key":"Pine & 5th","note":"15.2618"}]},{"panel":"numbers","set":{"Settled":"9"}},{"panel":"numbers","set":{"In queue":"5"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"5.607 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Take Main & 4th from the queue: 9 minutes so far plus a guess of 3.8138 to go makes 12.8138, the lowest in the queue.","ops":[{"v":"Main & 4th","state":"current"},{"panel":"queue","list":[{"key":"Market & 3rd","note":"13.8593"},{"key":"River & 1st","note":"14.0635"},{"key":"River & 2nd","note":"14.3228"},{"key":"Pine & 5th","note":"15.2618"}]},{"v":"Pine & 4th","state":"done"},{"panel":"numbers","set":{"Settled":"10"}},{"panel":"numbers","set":{"In queue":"4"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"3.8138 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Main & 4th to Main & 5th: 9 + 3 = 12. The guess from Main & 5th is 3.5276, so Main & 5th goes in the queue at 12 + 3.5276 = 15.5276.","ops":[{"v":"Main & 5th","state":"waiting"},{"e":["Main & 4th","Main & 5th"],"state":"tree"},{"panel":"dist","set":{"Main & 5th":"12"}},{"panel":"queue","list":[{"key":"Market & 3rd","note":"13.8593"},{"key":"River & 1st","note":"14.0635"},{"key":"River & 2nd","note":"14.3228"},{"key":"Pine & 5th","note":"15.2618"},{"key":"Main & 5th","note":"15.5276"}]},{"panel":"numbers","set":{"Settled":"10"}},{"panel":"numbers","set":{"In queue":"5"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"3.8138 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Main & 4th to Market & 4th: 9 + 2 = 11. The guess from Market & 4th is 2.6842, so Market & 4th goes in the queue at 11 + 2.6842 = 13.6842.","ops":[{"v":"Market & 4th","state":"waiting"},{"e":["Main & 4th","Market & 4th"],"state":"tree"},{"panel":"dist","set":{"Market & 4th":"11"}},{"panel":"queue","list":[{"key":"Market & 4th","note":"13.6842"},{"key":"Market & 3rd","note":"13.8593"},{"key":"River & 1st","note":"14.0635"},{"key":"River & 2nd","note":"14.3228"},{"key":"Pine & 5th","note":"15.2618"},{"key":"Main & 5th","note":"15.5276"}]},{"panel":"numbers","set":{"Settled":"10"}},{"panel":"numbers","set":{"In queue":"6"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"3.8138 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Take Market & 4th from the queue: 11 minutes so far plus a guess of 2.6842 to go makes 13.6842, the lowest in the queue.","ops":[{"v":"Market & 4th","state":"current"},{"panel":"queue","list":[{"key":"Market & 3rd","note":"13.8593"},{"key":"River & 1st","note":"14.0635"},{"key":"River & 2nd","note":"14.3228"},{"key":"Pine & 5th","note":"15.2618"},{"key":"Main & 5th","note":"15.5276"}]},{"v":"Main & 4th","state":"done"},{"panel":"numbers","set":{"Settled":"11"}},{"panel":"numbers","set":{"In queue":"5"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"2.6842 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Market & 4th to Market & 3rd: 11 + 3 = 14, not quicker than 10, so Market & 3rd stays in the queue at 13.8593.","ops":[{"e":["Market & 4th","Market & 3rd"],"state":"examined"}]},{"say":"Market & 4th to Market & 5th: 11 + 2 = 13. The guess from Market & 5th is 1.875, so Market & 5th goes in the queue at 13 + 1.875 = 14.875.","ops":[{"v":"Market & 5th","state":"waiting"},{"e":["Market & 4th","Market & 5th"],"state":"tree"},{"panel":"dist","set":{"Market & 5th":"13"}},{"panel":"queue","list":[{"key":"Market & 3rd","note":"13.8593"},{"key":"River & 1st","note":"14.0635"},{"key":"River & 2nd","note":"14.3228"},{"key":"Market & 5th","note":"14.875"},{"key":"Pine & 5th","note":"15.2618"},{"key":"Main & 5th","note":"15.5276"}]},{"panel":"numbers","set":{"Settled":"11"}},{"panel":"numbers","set":{"In queue":"6"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"2.6842 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Market & 4th to River & 4th: 11 + 3 = 14. The guess from River & 4th is 1.9608, so River & 4th goes in the queue at 14 + 1.9608 = 15.9608.","ops":[{"v":"River & 4th","state":"waiting"},{"e":["Market & 4th","River & 4th"],"state":"tree"},{"panel":"dist","set":{"River & 4th":"14"}},{"panel":"queue","list":[{"key":"Market & 3rd","note":"13.8593"},{"key":"River & 1st","note":"14.0635"},{"key":"River & 2nd","note":"14.3228"},{"key":"Market & 5th","note":"14.875"},{"key":"Pine & 5th","note":"15.2618"},{"key":"Main & 5th","note":"15.5276"},{"key":"River & 4th","note":"15.9608"}]},{"panel":"numbers","set":{"Settled":"11"}},{"panel":"numbers","set":{"In queue":"7"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"2.6842 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Take Market & 3rd from the queue: 10 minutes so far plus a guess of 3.8593 to go makes 13.8593, the lowest in the queue.","ops":[{"v":"Market & 3rd","state":"current"},{"panel":"queue","list":[{"key":"River & 1st","note":"14.0635"},{"key":"River & 2nd","note":"14.3228"},{"key":"Market & 5th","note":"14.875"},{"key":"Pine & 5th","note":"15.2618"},{"key":"Main & 5th","note":"15.5276"},{"key":"River & 4th","note":"15.9608"}]},{"v":"Market & 4th","state":"done"},{"panel":"numbers","set":{"Settled":"12"}},{"panel":"numbers","set":{"In queue":"6"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"3.8593 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Market & 3rd to River & 3rd: 10 + 3 = 13. The guess from River & 3rd is 3.6299, so River & 3rd goes in the queue at 13 + 3.6299 = 16.6299.","ops":[{"v":"River & 3rd","state":"waiting"},{"e":["Market & 3rd","River & 3rd"],"state":"tree"},{"panel":"dist","set":{"River & 3rd":"13"}},{"panel":"queue","list":[{"key":"River & 1st","note":"14.0635"},{"key":"River & 2nd","note":"14.3228"},{"key":"Market & 5th","note":"14.875"},{"key":"Pine & 5th","note":"15.2618"},{"key":"Main & 5th","note":"15.5276"},{"key":"River & 4th","note":"15.9608"},{"key":"River & 3rd","note":"16.6299"}]},{"panel":"numbers","set":{"Settled":"12"}},{"panel":"numbers","set":{"In queue":"7"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"3.8593 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Take River & 1st from the queue: 7 minutes so far plus a guess of 7.0635 to go makes 14.0635, the lowest in the queue.","ops":[{"v":"River & 1st","state":"current"},{"panel":"queue","list":[{"key":"River & 2nd","note":"14.3228"},{"key":"Market & 5th","note":"14.875"},{"key":"Pine & 5th","note":"15.2618"},{"key":"Main & 5th","note":"15.5276"},{"key":"River & 4th","note":"15.9608"},{"key":"River & 3rd","note":"16.6299"}]},{"v":"Market & 3rd","state":"done"},{"panel":"numbers","set":{"Settled":"13"}},{"panel":"numbers","set":{"In queue":"6"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"7.0635 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"River & 1st to River & 2nd: 7 + 3 = 10, not quicker than 9, so River & 2nd stays in the queue at 14.3228.","ops":[{"e":["River & 1st","River & 2nd"],"state":"examined"}]},{"say":"Take River & 2nd from the queue: 9 minutes so far plus a guess of 5.3228 to go makes 14.3228, the lowest in the queue.","ops":[{"v":"River & 2nd","state":"current"},{"panel":"queue","list":[{"key":"Market & 5th","note":"14.875"},{"key":"Pine & 5th","note":"15.2618"},{"key":"Main & 5th","note":"15.5276"},{"key":"River & 4th","note":"15.9608"},{"key":"River & 3rd","note":"16.6299"}]},{"v":"River & 1st","state":"done"},{"panel":"numbers","set":{"Settled":"14"}},{"panel":"numbers","set":{"In queue":"5"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"5.3228 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"River & 2nd to River & 3rd: 9 + 2 = 11, quicker than 13, so River & 3rd moves up the queue to 11 + 3.6299 = 14.6299.","ops":[{"e":["Market & 3rd","River & 3rd"],"state":"examined"},{"e":["River & 2nd","River & 3rd"],"state":"tree"},{"panel":"dist","set":{"River & 3rd":"11"}},{"panel":"queue","list":[{"key":"River & 3rd","note":"14.6299"},{"key":"Market & 5th","note":"14.875"},{"key":"Pine & 5th","note":"15.2618"},{"key":"Main & 5th","note":"15.5276"},{"key":"River & 4th","note":"15.9608"}]},{"panel":"numbers","set":{"Settled":"14"}},{"panel":"numbers","set":{"In queue":"5"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"5.3228 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Take River & 3rd from the queue: 11 minutes so far plus a guess of 3.6299 to go makes 14.6299, the lowest in the queue.","ops":[{"v":"River & 3rd","state":"current"},{"panel":"queue","list":[{"key":"Market & 5th","note":"14.875"},{"key":"Pine & 5th","note":"15.2618"},{"key":"Main & 5th","note":"15.5276"},{"key":"River & 4th","note":"15.9608"}]},{"v":"River & 2nd","state":"done"},{"panel":"numbers","set":{"Settled":"15"}},{"panel":"numbers","set":{"In queue":"4"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"3.6299 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"River & 3rd to River & 4th: 11 + 2 = 13, quicker than 14, so River & 4th moves up the queue to 13 + 1.9608 = 14.9608.","ops":[{"e":["Market & 4th","River & 4th"],"state":"examined"},{"e":["River & 3rd","River & 4th"],"state":"tree"},{"panel":"dist","set":{"River & 4th":"13"}},{"panel":"queue","list":[{"key":"Market & 5th","note":"14.875"},{"key":"River & 4th","note":"14.9608"},{"key":"Pine & 5th","note":"15.2618"},{"key":"Main & 5th","note":"15.5276"}]},{"panel":"numbers","set":{"Settled":"15"}},{"panel":"numbers","set":{"In queue":"4"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"3.6299 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Take Market & 5th from the queue: 13 minutes so far plus a guess of 1.875 to go makes 14.875, the lowest in the queue.","ops":[{"v":"Market & 5th","state":"current"},{"panel":"queue","list":[{"key":"River & 4th","note":"14.9608"},{"key":"Pine & 5th","note":"15.2618"},{"key":"Main & 5th","note":"15.5276"}]},{"v":"River & 3rd","state":"done"},{"panel":"numbers","set":{"Settled":"16"}},{"panel":"numbers","set":{"In queue":"3"}},{"panel":"numbers","set":{"Best time to goal":"–"}},{"panel":"numbers","set":{"Guess to goal":"1.875 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Market & 5th to Main & 5th: 13 + 2 = 15, not quicker than 12, so Main & 5th stays in the queue at 15.5276.","ops":[{"e":["Market & 5th","Main & 5th"],"state":"examined"}]},{"say":"Market & 5th to River & 5th: 13 + 2 = 15. The guess from River & 5th is 0, so River & 5th goes in the queue at 15 + 0 = 15.","ops":[{"v":"River & 5th","state":"waiting"},{"e":["Market & 5th","River & 5th"],"state":"tree"},{"panel":"dist","set":{"River & 5th":"15"}},{"panel":"queue","list":[{"key":"River & 4th","note":"14.9608"},{"key":"River & 5th","note":"15"},{"key":"Pine & 5th","note":"15.2618"},{"key":"Main & 5th","note":"15.5276"}]},{"panel":"numbers","set":{"Settled":"16"}},{"panel":"numbers","set":{"In queue":"4"}},{"panel":"numbers","set":{"Best time to goal":"15 min"}},{"panel":"numbers","set":{"Guess to goal":"1.875 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Take River & 4th from the queue: 13 minutes so far plus a guess of 1.9608 to go makes 14.9608, the lowest in the queue.","ops":[{"v":"River & 4th","state":"current"},{"panel":"queue","list":[{"key":"River & 5th","note":"15"},{"key":"Pine & 5th","note":"15.2618"},{"key":"Main & 5th","note":"15.5276"}]},{"v":"Market & 5th","state":"done"},{"panel":"numbers","set":{"Settled":"17"}},{"panel":"numbers","set":{"In queue":"3"}},{"panel":"numbers","set":{"Best time to goal":"15 min"}},{"panel":"numbers","set":{"Guess to goal":"1.9608 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"River & 4th to River & 5th: 13 + 4 = 17, not quicker than 15, so River & 5th stays in the queue at 15.","ops":[{"e":["River & 4th","River & 5th"],"state":"examined"}]},{"say":"Take River & 5th from the queue at 15 minutes. That's the goal, so the quickest route there is known, and A* stops. It settled 18 vertices, where Dijkstra settles 20 by the time it reaches River & 5th.","ops":[{"v":"River & 5th","state":"current"},{"panel":"queue","list":[{"key":"Pine & 5th","note":"15.2618"},{"key":"Main & 5th","note":"15.5276"}]},{"v":"River & 4th","state":"done"},{"panel":"numbers","set":{"Settled":"18"}},{"panel":"numbers","set":{"In queue":"2"}},{"panel":"numbers","set":{"Best time to goal":"15 min"}},{"panel":"numbers","set":{"Guess to goal":"0 min"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]}],"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[\"River & 5th\"]\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, \"Pine & 1st\", \"River & 5th\", 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}"}
