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