{"algorithm":"closest-first","about":["Closest-first keeps a priority queue of vertices by their distance from the start, the sum of the edge weights along the best path found so far. It takes the nearest vertex it hasn't visited, then puts each unvisited neighbor in the queue at the distance through that vertex, or moves it up the queue if that distance is shorter than the one it has. The vertices come out in order of distance, nearest first.","It is Dijkstra's algorithm as an iterator. traverse.ClosestFirst returns an iter.Seq2 of each vertex with its distance, and each one it yields is final, so a range loop can break at the vertex it needs without settling the rest of the graph. It costs O(E log V). Edge weights must not be negative, or a vertex can come out before a cheaper path to it is found.","Use it when the order matters, such as the three stores nearest to a home, and path.Dijkstra when you need the distance to every vertex at once."],"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":"List the places you can drive to from home, nearest by travel time first.","params":{"start":"Home"},"result":{"kind":"order","vertices":["Home","Bridge","Bakery","Park","Library","School"]},"answer":"From Home, closest-first visits 6 vertices, nearest first: Home, Bridge, Bakery, Park, Library and 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":"Current","color":"#56B4E9","shape":"ring"},{"id":"done","label":"Visited","color":"#009E73","shape":"filled"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"tree","label":"Used to reach a vertex","color":"#009E73","shape":"thick"},{"id":"examined","label":"Checked, not used","color":"#CC79A7","shape":"dashed"}],"panels":[{"id":"queue","title":"Priority queue","kind":"list"},{"id":"dist","title":"Distances","kind":"table"},{"id":"order","title":"Visit order","kind":"list"}]},"steps":[{"say":"Every distance starts at ∞, except Home, which is 0. Put Home in the queue at 0.","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 front of the queue and visit it. Its distance is 0.","ops":[{"v":"Home","state":"current"},{"panel":"queue","list":[]},{"panel":"order","list":[{"key":"Home"}]}]},{"say":"Home to Bakery: 0 + 4 = 4. Put Bakery in the queue at 4.","ops":[{"v":"Bakery","state":"waiting"},{"panel":"dist","set":{"Bakery":"4"}},{"e":["Home","Bakery"],"state":"examined"},{"panel":"queue","list":[{"key":"Bakery","note":"4"}]}]},{"say":"Home to Bridge: 0 + 3 = 3. Put Bridge in the queue at 3.","ops":[{"v":"Bridge","state":"waiting"},{"panel":"dist","set":{"Bridge":"3"}},{"e":["Home","Bridge"],"state":"examined"},{"panel":"queue","list":[{"key":"Bridge","note":"3"},{"key":"Bakery","note":"4"}]}]},{"say":"Take Bridge from the front of the queue and visit it. Its distance is 3.","ops":[{"v":"Bridge","state":"current"},{"panel":"queue","list":[{"key":"Bakery","note":"4"}]},{"panel":"order","list":[{"key":"Home"},{"key":"Bridge"}]},{"e":["Home","Bridge"],"state":"tree"},{"v":"Home","state":"done"}]},{"say":"Bridge to Park: 3 + 2 = 5. Put Park in the queue at 5.","ops":[{"v":"Park","state":"waiting"},{"panel":"dist","set":{"Park":"5"}},{"e":["Bridge","Park"],"state":"examined"},{"panel":"queue","list":[{"key":"Bakery","note":"4"},{"key":"Park","note":"5"}]}]},{"say":"Take Bakery from the front of the queue and visit it. Its distance is 4.","ops":[{"v":"Bakery","state":"current"},{"panel":"queue","list":[{"key":"Park","note":"5"}]},{"panel":"order","list":[{"key":"Home"},{"key":"Bridge"},{"key":"Bakery"}]},{"e":["Home","Bakery"],"state":"tree"},{"v":"Bridge","state":"done"}]},{"say":"Bakery to Park: 4 + 3 = 7, not shorter than 5. Park stays in the queue at 5.","ops":[{"e":["Bakery","Park"],"state":"examined"},{"panel":"queue","list":[{"key":"Park","note":"5"}]}]},{"say":"Take Park from the front of the queue and visit it. Its distance is 5.","ops":[{"v":"Park","state":"current"},{"panel":"queue","list":[]},{"panel":"order","list":[{"key":"Home"},{"key":"Bridge"},{"key":"Bakery"},{"key":"Park"}]},{"e":["Bridge","Park"],"state":"tree"},{"v":"Bakery","state":"done"}]},{"say":"Park to Library: 5 + 4 = 9. Put Library in the queue at 9.","ops":[{"v":"Library","state":"waiting"},{"panel":"dist","set":{"Library":"9"}},{"e":["Park","Library"],"state":"examined"},{"panel":"queue","list":[{"key":"Library","note":"9"}]}]},{"say":"Park to School: 5 + 7 = 12. Put School in the queue at 12.","ops":[{"v":"School","state":"waiting"},{"panel":"dist","set":{"School":"12"}},{"e":["Park","School"],"state":"examined"},{"panel":"queue","list":[{"key":"Library","note":"9"},{"key":"School","note":"12"}]}]},{"say":"Take Library from the front of the queue and visit it. Its distance is 9.","ops":[{"v":"Library","state":"current"},{"panel":"queue","list":[{"key":"School","note":"12"}]},{"panel":"order","list":[{"key":"Home"},{"key":"Bridge"},{"key":"Bakery"},{"key":"Park"},{"key":"Library"}]},{"e":["Park","Library"],"state":"tree"},{"v":"Park","state":"done"}]},{"say":"Library to School: 9 + 2 = 11, shorter than 12. Move School up the queue to 11.","ops":[{"panel":"dist","set":{"School":"11"}},{"e":["Library","School"],"state":"examined"},{"panel":"queue","list":[{"key":"School","note":"11"}]}]},{"say":"Take School from the front of the queue and visit it. Its distance is 11. It has no unvisited neighbors.","ops":[{"v":"School","state":"current"},{"panel":"queue","list":[]},{"panel":"order","list":[{"key":"Home"},{"key":"Bridge"},{"key":"Bakery"},{"key":"Park"},{"key":"Library"},{"key":"School"}]},{"e":["Library","School"],"state":"tree"},{"v":"Library","state":"done"}]},{"say":"Done. Closest-first visited 6 vertices from Home, nearest first.","ops":[{"v":"School","state":"done"}]}],"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":"for v, dist := range traverse.ClosestFirst(g, \"Home\") {\n\tfmt.Println(v.Label(), dist)\n}"}
