{"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":"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":"List the stops a driver can reach from the depot, nearest by travel time first.","params":{"start":"Depot"},"result":{"kind":"order","vertices":["Depot","Market","Bakery","School","Park","Library","Clinic","Station"]},"answer":"From Depot, closest-first visits 8 vertices, nearest first: Depot, Market, Bakery, School, Park, Library, Clinic and 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":"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 Depot, which is 0. Put Depot in the queue at 0.","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 front of the queue and visit it. Its distance is 0.","ops":[{"v":"Depot","state":"current"},{"panel":"queue","list":[]},{"panel":"order","list":[{"key":"Depot"}]}]},{"say":"Depot to Bakery: 0 + 4 = 4. Put Bakery in the queue at 4.","ops":[{"v":"Bakery","state":"waiting"},{"panel":"dist","set":{"Bakery":"4"}},{"e":["Depot","Bakery"],"state":"examined"},{"panel":"queue","list":[{"key":"Bakery","note":"4"}]}]},{"say":"Depot to Market: 0 + 2 = 2. Put Market in the queue at 2.","ops":[{"v":"Market","state":"waiting"},{"panel":"dist","set":{"Market":"2"}},{"e":["Depot","Market"],"state":"examined"},{"panel":"queue","list":[{"key":"Market","note":"2"},{"key":"Bakery","note":"4"}]}]},{"say":"Take Market from the front of the queue and visit it. Its distance is 2.","ops":[{"v":"Market","state":"current"},{"panel":"queue","list":[{"key":"Bakery","note":"4"}]},{"panel":"order","list":[{"key":"Depot"},{"key":"Market"}]},{"e":["Depot","Market"],"state":"tree"},{"v":"Depot","state":"done"}]},{"say":"Market to Bakery: 2 + 1 = 3, shorter than 4. Move Bakery up the queue to 3.","ops":[{"panel":"dist","set":{"Bakery":"3"}},{"e":["Market","Bakery"],"state":"examined"},{"panel":"queue","list":[{"key":"Bakery","note":"3"}]}]},{"say":"Market to Park: 2 + 8 = 10. Put Park in the queue at 10.","ops":[{"v":"Park","state":"waiting"},{"panel":"dist","set":{"Park":"10"}},{"e":["Market","Park"],"state":"examined"},{"panel":"queue","list":[{"key":"Bakery","note":"3"},{"key":"Park","note":"10"}]}]},{"say":"Market to Clinic: 2 + 10 = 12. Put Clinic in the queue at 12.","ops":[{"v":"Clinic","state":"waiting"},{"panel":"dist","set":{"Clinic":"12"}},{"e":["Market","Clinic"],"state":"examined"},{"panel":"queue","list":[{"key":"Bakery","note":"3"},{"key":"Park","note":"10"},{"key":"Clinic","note":"12"}]}]},{"say":"Take Bakery from the front of the queue and visit it. Its distance is 3.","ops":[{"v":"Bakery","state":"current"},{"panel":"queue","list":[{"key":"Park","note":"10"},{"key":"Clinic","note":"12"}]},{"panel":"order","list":[{"key":"Depot"},{"key":"Market"},{"key":"Bakery"}]},{"e":["Market","Bakery"],"state":"tree"},{"v":"Market","state":"done"}]},{"say":"Bakery to School: 3 + 5 = 8. Put School in the queue at 8.","ops":[{"v":"School","state":"waiting"},{"panel":"dist","set":{"School":"8"}},{"e":["Bakery","School"],"state":"examined"},{"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. Park stays in the queue at 10.","ops":[{"e":["Bakery","Park"],"state":"examined"},{"panel":"queue","list":[{"key":"School","note":"8"},{"key":"Park","note":"10"},{"key":"Clinic","note":"12"}]}]},{"say":"Take School from the front of the queue and visit it. Its distance is 8.","ops":[{"v":"School","state":"current"},{"panel":"queue","list":[{"key":"Park","note":"10"},{"key":"Clinic","note":"12"}]},{"panel":"order","list":[{"key":"Depot"},{"key":"Market"},{"key":"Bakery"},{"key":"School"}]},{"e":["Bakery","School"],"state":"tree"},{"v":"Bakery","state":"done"}]},{"say":"School to Library: 8 + 3 = 11. Put Library in the queue at 11.","ops":[{"v":"Library","state":"waiting"},{"panel":"dist","set":{"Library":"11"}},{"e":["School","Library"],"state":"examined"},{"panel":"queue","list":[{"key":"Park","note":"10"},{"key":"Library","note":"11"},{"key":"Clinic","note":"12"}]}]},{"say":"Take Park from the front of the queue and visit it. Its distance is 10.","ops":[{"v":"Park","state":"current"},{"panel":"queue","list":[{"key":"Library","note":"11"},{"key":"Clinic","note":"12"}]},{"panel":"order","list":[{"key":"Depot"},{"key":"Market"},{"key":"Bakery"},{"key":"School"},{"key":"Park"}]},{"e":["Market","Park"],"state":"tree"},{"v":"School","state":"done"}]},{"say":"Park to Library: 10 + 2 = 12, not shorter than 11. Library stays in the queue at 11.","ops":[{"e":["Park","Library"],"state":"examined"},{"panel":"queue","list":[{"key":"Library","note":"11"},{"key":"Clinic","note":"12"}]}]},{"say":"Park to Station: 10 + 6 = 16. Put Station in the queue at 16.","ops":[{"v":"Station","state":"waiting"},{"panel":"dist","set":{"Station":"16"}},{"e":["Park","Station"],"state":"examined"},{"panel":"queue","list":[{"key":"Library","note":"11"},{"key":"Clinic","note":"12"},{"key":"Station","note":"16"}]}]},{"say":"Take Library from the front of the queue and visit it. Its distance is 11.","ops":[{"v":"Library","state":"current"},{"panel":"queue","list":[{"key":"Clinic","note":"12"},{"key":"Station","note":"16"}]},{"panel":"order","list":[{"key":"Depot"},{"key":"Market"},{"key":"Bakery"},{"key":"School"},{"key":"Park"},{"key":"Library"}]},{"e":["School","Library"],"state":"tree"},{"v":"Park","state":"done"}]},{"say":"Library to Station: 11 + 5 = 16, not shorter than 16. Station stays in the queue at 16.","ops":[{"e":["Library","Station"],"state":"examined"},{"panel":"queue","list":[{"key":"Clinic","note":"12"},{"key":"Station","note":"16"}]}]},{"say":"Take Clinic from the front of the queue and visit it. Its distance is 12.","ops":[{"v":"Clinic","state":"current"},{"panel":"queue","list":[{"key":"Station","note":"16"}]},{"panel":"order","list":[{"key":"Depot"},{"key":"Market"},{"key":"Bakery"},{"key":"School"},{"key":"Park"},{"key":"Library"},{"key":"Clinic"}]},{"e":["Market","Clinic"],"state":"tree"},{"v":"Library","state":"done"}]},{"say":"Clinic to Station: 12 + 2 = 14, shorter than 16. Move Station up the queue to 14.","ops":[{"panel":"dist","set":{"Station":"14"}},{"e":["Clinic","Station"],"state":"examined"},{"panel":"queue","list":[{"key":"Station","note":"14"}]}]},{"say":"Take Station from the front of the queue and visit it. Its distance is 14. It has no unvisited neighbors.","ops":[{"v":"Station","state":"current"},{"panel":"queue","list":[]},{"panel":"order","list":[{"key":"Depot"},{"key":"Market"},{"key":"Bakery"},{"key":"School"},{"key":"Park"},{"key":"Library"},{"key":"Clinic"},{"key":"Station"}]},{"e":["Clinic","Station"],"state":"tree"},{"v":"Clinic","state":"done"}]},{"say":"Done. Closest-first visited 8 vertices from Depot, nearest first.","ops":[{"v":"Station","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, \"Depot\") {\n\tfmt.Println(v.Label(), dist)\n}"}
