{"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":"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":"How many minutes is the quickest drive from the depot to each stop?","params":{"start":"Depot"},"result":{"kind":"distances","values":{"Bakery":3,"Clinic":12,"Depot":0,"Library":11,"Market":2,"Park":10,"School":8,"Station":14}},"answer":"From Depot, the shortest distances are 2 to Market, 3 to Bakery, 8 to School, 10 to Park, 11 to Library, 12 to Clinic and 14 to Station.","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 Depot, which is 0. Put Depot in the queue.","ops":[{"v":"Depot","state":"waiting"},{"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":"queue","list":[{"key":"Depot","note":"0"}]}]},{"say":"Take Depot from the queue. Its distance, 0, is now final.","ops":[{"v":"Depot","state":"current"},{"panel":"queue","list":[]}]},{"say":"Depot to Bakery: 0 + 4 = 4, so Bakery's distance becomes 4. Put Bakery in the queue.","ops":[{"v":"Bakery","state":"waiting"},{"e":["Depot","Bakery"],"state":"tree"},{"panel":"dist","set":{"Bakery":"4"}},{"panel":"queue","list":[{"key":"Bakery","note":"4"}]}]},{"say":"Depot to Market: 0 + 2 = 2, so Market's distance becomes 2. Put Market in the queue.","ops":[{"v":"Market","state":"waiting"},{"e":["Depot","Market"],"state":"tree"},{"panel":"dist","set":{"Market":"2"}},{"panel":"queue","list":[{"key":"Market","note":"2"},{"key":"Bakery","note":"4"}]}]},{"say":"Take Market from the queue. Its distance, 2, is now final.","ops":[{"v":"Market","state":"current"},{"panel":"queue","list":[{"key":"Bakery","note":"4"}]},{"v":"Depot","state":"done"}]},{"say":"Market to Bakery: 2 + 1 = 3, shorter than 4, so Bakery's distance becomes 3. Move Bakery up the queue.","ops":[{"e":["Market","Bakery"],"state":"tree"},{"e":["Depot","Bakery"],"state":"examined"},{"panel":"dist","set":{"Bakery":"3"}},{"panel":"queue","list":[{"key":"Bakery","note":"3"}]}]},{"say":"Market to Park: 2 + 8 = 10, so Park's distance becomes 10. Put Park in the queue.","ops":[{"v":"Park","state":"waiting"},{"e":["Market","Park"],"state":"tree"},{"panel":"dist","set":{"Park":"10"}},{"panel":"queue","list":[{"key":"Bakery","note":"3"},{"key":"Park","note":"10"}]}]},{"say":"Market to Clinic: 2 + 10 = 12, so Clinic's distance becomes 12. Put Clinic in the queue.","ops":[{"v":"Clinic","state":"waiting"},{"e":["Market","Clinic"],"state":"tree"},{"panel":"dist","set":{"Clinic":"12"}},{"panel":"queue","list":[{"key":"Bakery","note":"3"},{"key":"Park","note":"10"},{"key":"Clinic","note":"12"}]}]},{"say":"Take Bakery from the queue. Its distance, 3, is now final.","ops":[{"v":"Bakery","state":"current"},{"panel":"queue","list":[{"key":"Park","note":"10"},{"key":"Clinic","note":"12"}]},{"v":"Market","state":"done"}]},{"say":"Bakery to School: 3 + 5 = 8, so School's distance becomes 8. Put School in the queue.","ops":[{"v":"School","state":"waiting"},{"e":["Bakery","School"],"state":"tree"},{"panel":"dist","set":{"School":"8"}},{"panel":"queue","list":[{"key":"School","note":"8"},{"key":"Park","note":"10"},{"key":"Clinic","note":"12"}]}]},{"say":"Bakery to Park: 3 + 7 = 10, not shorter than 10, so Park keeps 10.","ops":[{"e":["Bakery","Park"],"state":"examined"}]},{"say":"Take School from the queue. Its distance, 8, is now final.","ops":[{"v":"School","state":"current"},{"panel":"queue","list":[{"key":"Park","note":"10"},{"key":"Clinic","note":"12"}]},{"v":"Bakery","state":"done"}]},{"say":"School to Library: 8 + 3 = 11, so Library's distance becomes 11. Put Library in the queue.","ops":[{"v":"Library","state":"waiting"},{"e":["School","Library"],"state":"tree"},{"panel":"dist","set":{"Library":"11"}},{"panel":"queue","list":[{"key":"Park","note":"10"},{"key":"Library","note":"11"},{"key":"Clinic","note":"12"}]}]},{"say":"Take Park from the queue. Its distance, 10, is now final.","ops":[{"v":"Park","state":"current"},{"panel":"queue","list":[{"key":"Library","note":"11"},{"key":"Clinic","note":"12"}]},{"v":"School","state":"done"}]},{"say":"Park to Library: 10 + 2 = 12, not shorter than 11, so Library keeps 11.","ops":[{"e":["Park","Library"],"state":"examined"}]},{"say":"Park to Station: 10 + 6 = 16, so Station's distance becomes 16. Put Station in the queue.","ops":[{"v":"Station","state":"waiting"},{"e":["Park","Station"],"state":"tree"},{"panel":"dist","set":{"Station":"16"}},{"panel":"queue","list":[{"key":"Library","note":"11"},{"key":"Clinic","note":"12"},{"key":"Station","note":"16"}]}]},{"say":"Take Library from the queue. Its distance, 11, is now final.","ops":[{"v":"Library","state":"current"},{"panel":"queue","list":[{"key":"Clinic","note":"12"},{"key":"Station","note":"16"}]},{"v":"Park","state":"done"}]},{"say":"Library to Station: 11 + 5 = 16, not shorter than 16, so Station keeps 16.","ops":[{"e":["Library","Station"],"state":"examined"}]},{"say":"Take Clinic from the queue. Its distance, 12, is now final.","ops":[{"v":"Clinic","state":"current"},{"panel":"queue","list":[{"key":"Station","note":"16"}]},{"v":"Library","state":"done"}]},{"say":"Clinic to Station: 12 + 2 = 14, shorter than 16, so Station's distance becomes 14. Move Station up the queue.","ops":[{"e":["Clinic","Station"],"state":"tree"},{"e":["Park","Station"],"state":"examined"},{"panel":"dist","set":{"Station":"14"}},{"panel":"queue","list":[{"key":"Station","note":"14"}]}]},{"say":"Take Station from the queue. Its distance, 14, is now final. It has no unsettled neighbors.","ops":[{"v":"Station","state":"current"},{"panel":"queue","list":[]},{"v":"Clinic","state":"done"}]},{"say":"Done. Every distance from Depot is final.","ops":[{"v":"Station","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, \"Depot\")\nif err != nil {\n\treturn err\n}\nminutes, ok := paths.Distance(\"Station\")\nif !ok {\n\treturn nil // out of reach\n}\nroute, _ := paths.PathTo(\"Station\")\nfmt.Println(minutes)\nfor _, v := range route {\n\tfmt.Println(v.Label())\n}"}
