{"algorithm":"dijkstra","about":["Dijkstra's algorithm gives the start a distance of 0 and every other vertex a distance of infinity, and keeps the vertices in a priority queue by distance. It takes the closest vertex out, which makes its distance final, and checks each edge from it. When the path through that vertex is shorter than a neighbor's current distance, the neighbor takes the shorter distance, and the edge it came by becomes its way in.","This works because no edge weight is negative. Once a vertex is the closest one left, no later path can reach it for less. With a negative edge that stops being true, and Bellman-Ford is the one to use. path.DijkstraPaths keeps one entry per vertex in a binary heap and moves it up when a shorter path turns up, so it costs O((V+E) log V). It goes on until every vertex it can reach is settled.","Distance and PathTo on its result give each distance and the route there, start first, and report false for a vertex the start can't reach, so there's no infinity to compare with. Of two routes that are equally short, it keeps the one it found first, and vertices at the same distance leave the queue in the order of the edges that reached them, so the same graph gives the same routes on every run.","path.Dijkstra returns the distances alone, with math.MaxFloat64 for a vertex it can't reach, and path.DijkstraSimple returns them with a plain list and a linear scan instead of a heap, in O(V²). The performance card on this page times all three on each example graph."],"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":"How many minutes is the quickest drive from Pine & 1st to each intersection, with Market closed between 2nd and 3rd?","params":{"start":"Pine & 1st"},"result":{"kind":"distances","values":{"Main \u0026 1st":2,"Main \u0026 2nd":5,"Main \u0026 3rd":7,"Main \u0026 4th":9,"Main \u0026 5th":12,"Market \u0026 1st":5,"Market \u0026 2nd":7,"Market \u0026 3rd":10,"Market \u0026 4th":11,"Market \u0026 5th":13,"Pine \u0026 1st":0,"Pine \u0026 2nd":2,"Pine \u0026 3rd":5,"Pine \u0026 4th":7,"Pine \u0026 5th":10,"River \u0026 1st":7,"River \u0026 2nd":9,"River \u0026 3rd":11,"River \u0026 4th":13,"River \u0026 5th":15}},"answer":"From Pine & 1st, the shortest distances are 2 to Main & 1st, 2 to Pine & 2nd, 5 to Main & 2nd, 5 to Market & 1st, 5 to Pine & 3rd, 7 to Main & 3rd, 7 to Market & 2nd, 7 to Pine & 4th, 7 to River & 1st, 9 to Main & 4th and 9 more. The farthest is River & 5th, at 15.","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":"On a shortest path","color":"#009E73","shape":"thick"},{"id":"examined","label":"Checked, not shorter","color":"#CC79A7","shape":"dashed"}],"panels":[{"id":"queue","title":"Priority queue","kind":"list"},{"id":"dist","title":"Distances","kind":"table"}]},"steps":[{"say":"Every distance starts at ∞, except Pine & 1st, which is 0. Put Pine & 1st in the queue.","ops":[{"v":"Pine & 1st","state":"waiting"},{"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":"queue","list":[{"key":"Pine & 1st","note":"0"}]}]},{"say":"Take Pine & 1st from the queue. Its distance, 0, is now final.","ops":[{"v":"Pine & 1st","state":"current"},{"panel":"queue","list":[]}]},{"say":"Pine & 1st to Pine & 2nd: 0 + 2 = 2, so Pine & 2nd's distance becomes 2. Put Pine & 2nd in the queue.","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":"2"}]}]},{"say":"Pine & 1st to Main & 1st: 0 + 2 = 2, so Main & 1st's distance becomes 2. Put Main & 1st in the queue.","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":"2"},{"key":"Main & 1st","note":"2"}]}]},{"say":"Take Pine & 2nd from the queue. Its distance, 2, is now final.","ops":[{"v":"Pine & 2nd","state":"current"},{"panel":"queue","list":[{"key":"Main & 1st","note":"2"}]},{"v":"Pine & 1st","state":"done"}]},{"say":"Pine & 2nd to Pine & 3rd: 2 + 3 = 5, so Pine & 3rd's distance becomes 5. Put Pine & 3rd in the queue.","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":"2"},{"key":"Pine & 3rd","note":"5"}]}]},{"say":"Pine & 2nd to Main & 2nd: 2 + 3 = 5, so Main & 2nd's distance becomes 5. Put Main & 2nd in the queue.","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":"2"},{"key":"Pine & 3rd","note":"5"},{"key":"Main & 2nd","note":"5"}]}]},{"say":"Take Main & 1st from the queue. Its distance, 2, is now final.","ops":[{"v":"Main & 1st","state":"current"},{"panel":"queue","list":[{"key":"Pine & 3rd","note":"5"},{"key":"Main & 2nd","note":"5"}]},{"v":"Pine & 2nd","state":"done"}]},{"say":"Main & 1st to Main & 2nd: 2 + 3 = 5, not shorter than 5, so Main & 2nd keeps 5.","ops":[{"e":["Main & 1st","Main & 2nd"],"state":"examined"}]},{"say":"Main & 1st to Market & 1st: 2 + 3 = 5, so Market & 1st's distance becomes 5. Put Market & 1st in the queue.","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":"5"},{"key":"Main & 2nd","note":"5"},{"key":"Market & 1st","note":"5"}]}]},{"say":"Take Pine & 3rd from the queue. Its distance, 5, is now final.","ops":[{"v":"Pine & 3rd","state":"current"},{"panel":"queue","list":[{"key":"Main & 2nd","note":"5"},{"key":"Market & 1st","note":"5"}]},{"v":"Main & 1st","state":"done"}]},{"say":"Pine & 3rd to Pine & 4th: 5 + 2 = 7, so Pine & 4th's distance becomes 7. Put Pine & 4th in the queue.","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":"5"},{"key":"Market & 1st","note":"5"},{"key":"Pine & 4th","note":"7"}]}]},{"say":"Pine & 3rd to Main & 3rd: 5 + 2 = 7, so Main & 3rd's distance becomes 7. Put Main & 3rd in the queue.","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":"5"},{"key":"Market & 1st","note":"5"},{"key":"Pine & 4th","note":"7"},{"key":"Main & 3rd","note":"7"}]}]},{"say":"Take Main & 2nd from the queue. Its distance, 5, is now final.","ops":[{"v":"Main & 2nd","state":"current"},{"panel":"queue","list":[{"key":"Market & 1st","note":"5"},{"key":"Pine & 4th","note":"7"},{"key":"Main & 3rd","note":"7"}]},{"v":"Pine & 3rd","state":"done"}]},{"say":"Main & 2nd to Main & 3rd: 5 + 4 = 9, not shorter than 7, so Main & 3rd keeps 7.","ops":[{"e":["Main & 2nd","Main & 3rd"],"state":"examined"}]},{"say":"Main & 2nd to Market & 2nd: 5 + 2 = 7, so Market & 2nd's distance becomes 7. Put Market & 2nd in the queue.","ops":[{"v":"Market & 2nd","state":"waiting"},{"e":["Main & 2nd","Market & 2nd"],"state":"tree"},{"panel":"dist","set":{"Market & 2nd":"7"}},{"panel":"queue","list":[{"key":"Market & 1st","note":"5"},{"key":"Pine & 4th","note":"7"},{"key":"Main & 3rd","note":"7"},{"key":"Market & 2nd","note":"7"}]}]},{"say":"Take Market & 1st from the queue. Its distance, 5, is now final.","ops":[{"v":"Market & 1st","state":"current"},{"panel":"queue","list":[{"key":"Pine & 4th","note":"7"},{"key":"Main & 3rd","note":"7"},{"key":"Market & 2nd","note":"7"}]},{"v":"Main & 2nd","state":"done"}]},{"say":"Market & 1st to Market & 2nd: 5 + 2 = 7, not shorter than 7, so Market & 2nd keeps 7.","ops":[{"e":["Market & 1st","Market & 2nd"],"state":"examined"}]},{"say":"Market & 1st to River & 1st: 5 + 2 = 7, so River & 1st's distance becomes 7. Put River & 1st in the queue.","ops":[{"v":"River & 1st","state":"waiting"},{"e":["Market & 1st","River & 1st"],"state":"tree"},{"panel":"dist","set":{"River & 1st":"7"}},{"panel":"queue","list":[{"key":"Pine & 4th","note":"7"},{"key":"Main & 3rd","note":"7"},{"key":"Market & 2nd","note":"7"},{"key":"River & 1st","note":"7"}]}]},{"say":"Take Pine & 4th from the queue. Its distance, 7, is now final.","ops":[{"v":"Pine & 4th","state":"current"},{"panel":"queue","list":[{"key":"Main & 3rd","note":"7"},{"key":"Market & 2nd","note":"7"},{"key":"River & 1st","note":"7"}]},{"v":"Market & 1st","state":"done"}]},{"say":"Pine & 4th to Pine & 5th: 7 + 3 = 10, so Pine & 5th's distance becomes 10. Put Pine & 5th in the queue.","ops":[{"v":"Pine & 5th","state":"waiting"},{"e":["Pine & 4th","Pine & 5th"],"state":"tree"},{"panel":"dist","set":{"Pine & 5th":"10"}},{"panel":"queue","list":[{"key":"Main & 3rd","note":"7"},{"key":"Market & 2nd","note":"7"},{"key":"River & 1st","note":"7"},{"key":"Pine & 5th","note":"10"}]}]},{"say":"Pine & 4th to Main & 4th: 7 + 2 = 9, so Main & 4th's distance becomes 9. Put Main & 4th in the queue.","ops":[{"v":"Main & 4th","state":"waiting"},{"e":["Pine & 4th","Main & 4th"],"state":"tree"},{"panel":"dist","set":{"Main & 4th":"9"}},{"panel":"queue","list":[{"key":"Main & 3rd","note":"7"},{"key":"Market & 2nd","note":"7"},{"key":"River & 1st","note":"7"},{"key":"Main & 4th","note":"9"},{"key":"Pine & 5th","note":"10"}]}]},{"say":"Take Main & 3rd from the queue. Its distance, 7, is now final.","ops":[{"v":"Main & 3rd","state":"current"},{"panel":"queue","list":[{"key":"Market & 2nd","note":"7"},{"key":"River & 1st","note":"7"},{"key":"Main & 4th","note":"9"},{"key":"Pine & 5th","note":"10"}]},{"v":"Pine & 4th","state":"done"}]},{"say":"Main & 3rd to Main & 4th: 7 + 4 = 11, not shorter than 9, so Main & 4th keeps 9.","ops":[{"e":["Main & 3rd","Main & 4th"],"state":"examined"}]},{"say":"Main & 3rd to Market & 3rd: 7 + 3 = 10, so Market & 3rd's distance becomes 10. Put Market & 3rd in the queue.","ops":[{"v":"Market & 3rd","state":"waiting"},{"e":["Main & 3rd","Market & 3rd"],"state":"tree"},{"panel":"dist","set":{"Market & 3rd":"10"}},{"panel":"queue","list":[{"key":"Market & 2nd","note":"7"},{"key":"River & 1st","note":"7"},{"key":"Main & 4th","note":"9"},{"key":"Pine & 5th","note":"10"},{"key":"Market & 3rd","note":"10"}]}]},{"say":"Take Market & 2nd from the queue. Its distance, 7, is now final.","ops":[{"v":"Market & 2nd","state":"current"},{"panel":"queue","list":[{"key":"River & 1st","note":"7"},{"key":"Main & 4th","note":"9"},{"key":"Pine & 5th","note":"10"},{"key":"Market & 3rd","note":"10"}]},{"v":"Main & 3rd","state":"done"}]},{"say":"Market & 2nd to River & 2nd: 7 + 2 = 9, so River & 2nd's distance becomes 9. Put River & 2nd in the queue.","ops":[{"v":"River & 2nd","state":"waiting"},{"e":["Market & 2nd","River & 2nd"],"state":"tree"},{"panel":"dist","set":{"River & 2nd":"9"}},{"panel":"queue","list":[{"key":"River & 1st","note":"7"},{"key":"Main & 4th","note":"9"},{"key":"River & 2nd","note":"9"},{"key":"Pine & 5th","note":"10"},{"key":"Market & 3rd","note":"10"}]}]},{"say":"Take River & 1st from the queue. Its distance, 7, is now final.","ops":[{"v":"River & 1st","state":"current"},{"panel":"queue","list":[{"key":"Main & 4th","note":"9"},{"key":"River & 2nd","note":"9"},{"key":"Pine & 5th","note":"10"},{"key":"Market & 3rd","note":"10"}]},{"v":"Market & 2nd","state":"done"}]},{"say":"River & 1st to River & 2nd: 7 + 3 = 10, not shorter than 9, so River & 2nd keeps 9.","ops":[{"e":["River & 1st","River & 2nd"],"state":"examined"}]},{"say":"Take Main & 4th from the queue. Its distance, 9, is now final.","ops":[{"v":"Main & 4th","state":"current"},{"panel":"queue","list":[{"key":"River & 2nd","note":"9"},{"key":"Pine & 5th","note":"10"},{"key":"Market & 3rd","note":"10"}]},{"v":"River & 1st","state":"done"}]},{"say":"Main & 4th to Main & 5th: 9 + 3 = 12, so Main & 5th's distance becomes 12. Put Main & 5th in the queue.","ops":[{"v":"Main & 5th","state":"waiting"},{"e":["Main & 4th","Main & 5th"],"state":"tree"},{"panel":"dist","set":{"Main & 5th":"12"}},{"panel":"queue","list":[{"key":"River & 2nd","note":"9"},{"key":"Pine & 5th","note":"10"},{"key":"Market & 3rd","note":"10"},{"key":"Main & 5th","note":"12"}]}]},{"say":"Main & 4th to Market & 4th: 9 + 2 = 11, so Market & 4th's distance becomes 11. Put Market & 4th in the queue.","ops":[{"v":"Market & 4th","state":"waiting"},{"e":["Main & 4th","Market & 4th"],"state":"tree"},{"panel":"dist","set":{"Market & 4th":"11"}},{"panel":"queue","list":[{"key":"River & 2nd","note":"9"},{"key":"Pine & 5th","note":"10"},{"key":"Market & 3rd","note":"10"},{"key":"Market & 4th","note":"11"},{"key":"Main & 5th","note":"12"}]}]},{"say":"Take River & 2nd from the queue. Its distance, 9, is now final.","ops":[{"v":"River & 2nd","state":"current"},{"panel":"queue","list":[{"key":"Pine & 5th","note":"10"},{"key":"Market & 3rd","note":"10"},{"key":"Market & 4th","note":"11"},{"key":"Main & 5th","note":"12"}]},{"v":"Main & 4th","state":"done"}]},{"say":"River & 2nd to River & 3rd: 9 + 2 = 11, so River & 3rd's distance becomes 11. Put River & 3rd in the queue.","ops":[{"v":"River & 3rd","state":"waiting"},{"e":["River & 2nd","River & 3rd"],"state":"tree"},{"panel":"dist","set":{"River & 3rd":"11"}},{"panel":"queue","list":[{"key":"Pine & 5th","note":"10"},{"key":"Market & 3rd","note":"10"},{"key":"Market & 4th","note":"11"},{"key":"River & 3rd","note":"11"},{"key":"Main & 5th","note":"12"}]}]},{"say":"Take Pine & 5th from the queue. Its distance, 10, is now final.","ops":[{"v":"Pine & 5th","state":"current"},{"panel":"queue","list":[{"key":"Market & 3rd","note":"10"},{"key":"Market & 4th","note":"11"},{"key":"River & 3rd","note":"11"},{"key":"Main & 5th","note":"12"}]},{"v":"River & 2nd","state":"done"}]},{"say":"Pine & 5th to Main & 5th: 10 + 3 = 13, not shorter than 12, so Main & 5th keeps 12.","ops":[{"e":["Pine & 5th","Main & 5th"],"state":"examined"}]},{"say":"Take Market & 3rd from the queue. Its distance, 10, is now final.","ops":[{"v":"Market & 3rd","state":"current"},{"panel":"queue","list":[{"key":"Market & 4th","note":"11"},{"key":"River & 3rd","note":"11"},{"key":"Main & 5th","note":"12"}]},{"v":"Pine & 5th","state":"done"}]},{"say":"Market & 3rd to Market & 4th: 10 + 3 = 13, not shorter than 11, so Market & 4th keeps 11.","ops":[{"e":["Market & 3rd","Market & 4th"],"state":"examined"}]},{"say":"Market & 3rd to River & 3rd: 10 + 3 = 13, not shorter than 11, so River & 3rd keeps 11.","ops":[{"e":["Market & 3rd","River & 3rd"],"state":"examined"}]},{"say":"Take Market & 4th from the queue. Its distance, 11, is now final.","ops":[{"v":"Market & 4th","state":"current"},{"panel":"queue","list":[{"key":"River & 3rd","note":"11"},{"key":"Main & 5th","note":"12"}]},{"v":"Market & 3rd","state":"done"}]},{"say":"Market & 4th to Market & 5th: 11 + 2 = 13, so Market & 5th's distance becomes 13. Put Market & 5th in the queue.","ops":[{"v":"Market & 5th","state":"waiting"},{"e":["Market & 4th","Market & 5th"],"state":"tree"},{"panel":"dist","set":{"Market & 5th":"13"}},{"panel":"queue","list":[{"key":"River & 3rd","note":"11"},{"key":"Main & 5th","note":"12"},{"key":"Market & 5th","note":"13"}]}]},{"say":"Market & 4th to River & 4th: 11 + 3 = 14, so River & 4th's distance becomes 14. Put River & 4th in the queue.","ops":[{"v":"River & 4th","state":"waiting"},{"e":["Market & 4th","River & 4th"],"state":"tree"},{"panel":"dist","set":{"River & 4th":"14"}},{"panel":"queue","list":[{"key":"River & 3rd","note":"11"},{"key":"Main & 5th","note":"12"},{"key":"Market & 5th","note":"13"},{"key":"River & 4th","note":"14"}]}]},{"say":"Take River & 3rd from the queue. Its distance, 11, is now final.","ops":[{"v":"River & 3rd","state":"current"},{"panel":"queue","list":[{"key":"Main & 5th","note":"12"},{"key":"Market & 5th","note":"13"},{"key":"River & 4th","note":"14"}]},{"v":"Market & 4th","state":"done"}]},{"say":"River & 3rd to River & 4th: 11 + 2 = 13, shorter than 14, so River & 4th's distance becomes 13. Move River & 4th up the queue.","ops":[{"e":["River & 3rd","River & 4th"],"state":"tree"},{"e":["Market & 4th","River & 4th"],"state":"examined"},{"panel":"dist","set":{"River & 4th":"13"}},{"panel":"queue","list":[{"key":"Main & 5th","note":"12"},{"key":"Market & 5th","note":"13"},{"key":"River & 4th","note":"13"}]}]},{"say":"Take Main & 5th from the queue. Its distance, 12, is now final.","ops":[{"v":"Main & 5th","state":"current"},{"panel":"queue","list":[{"key":"Market & 5th","note":"13"},{"key":"River & 4th","note":"13"}]},{"v":"River & 3rd","state":"done"}]},{"say":"Main & 5th to Market & 5th: 12 + 2 = 14, not shorter than 13, so Market & 5th keeps 13.","ops":[{"e":["Main & 5th","Market & 5th"],"state":"examined"}]},{"say":"Take Market & 5th from the queue. Its distance, 13, is now final.","ops":[{"v":"Market & 5th","state":"current"},{"panel":"queue","list":[{"key":"River & 4th","note":"13"}]},{"v":"Main & 5th","state":"done"}]},{"say":"Market & 5th to River & 5th: 13 + 2 = 15, so River & 5th's distance becomes 15. Put River & 5th in the queue.","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":"13"},{"key":"River & 5th","note":"15"}]}]},{"say":"Take River & 4th from the queue. Its distance, 13, is now final.","ops":[{"v":"River & 4th","state":"current"},{"panel":"queue","list":[{"key":"River & 5th","note":"15"}]},{"v":"Market & 5th","state":"done"}]},{"say":"River & 4th to River & 5th: 13 + 4 = 17, not shorter than 15, so River & 5th keeps 15.","ops":[{"e":["River & 4th","River & 5th"],"state":"examined"}]},{"say":"Take River & 5th from the queue. Its distance, 15, is now final. It has no unsettled neighbors.","ops":[{"v":"River & 5th","state":"current"},{"panel":"queue","list":[]},{"v":"River & 4th","state":"done"}]},{"say":"Done. Every distance from Pine & 1st is final.","ops":[{"v":"River & 5th","state":"done"}]}],"traceNote":"","verification":"The steps come from a step-by-step copy of the algorithm. Its distances and the route it draws to each vertex are checked against Distance and PathTo of path.DijkstraPaths on every start.","snippet":"paths, err := path.DijkstraPaths(g, \"Pine & 1st\")\nif err != nil {\n\treturn err\n}\nminutes, ok := paths.Distance(\"River & 5th\")\nif !ok {\n\treturn nil // out of reach\n}\nroute, _ := paths.PathTo(\"River & 5th\")\nfmt.Println(minutes)\nfor _, v := range route {\n\tfmt.Println(v.Label())\n}"}
