{"algorithm":"k-center","about":["Where should a company open k warehouses so that no address is a long drive from all of them? Trying every choice is far too slow on a city, so path.KCenter chooses them farthest first: it opens the first warehouse, then keeps opening the next one at the address farthest from every warehouse so far. Each new warehouse needs a search only over the addresses it gets closer to, and k rounds cost O(k (V+E) log V).","When every road works both ways in the same time, the longest drive this leaves is never more than twice the best any k warehouses can do. With one-way streets the drives aren't symmetric, and that factor of two isn't guaranteed.","The second warehouse often lands at the edge of the map. The method shrinks the worst drive, so it serves the most remote address first. That is the difference from k-median, which minimizes the average drive and puts warehouses nearer the busy middle.","Warehouses that are already open can be passed as fixed centers. They count toward k and open first, in the order given. Without them, the first center is the first vertex added to the graph. Which one opens first changes the rest."],"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":"With one warehouse at Home, where should a second open so that the longest drive to any of the six places is as short as it can be made?","params":{"k":2,"sources":["Home"]},"result":{"kind":"order","vertices":["Home","School"]},"answer":"Open warehouses at Home and School, in that order. The longest drive is 5. The best of all 15 ways to choose 2 is 4.","legend":{"vertex":[{"id":"idle","label":"No warehouse reaches it yet","color":"#64748B","shape":"hollow"},{"id":"waiting","label":"In the queue","color":"#E69F00","shape":"dashed-square"},{"id":"current","label":"Being settled","color":"#56B4E9","shape":"ring"},{"id":"farthest","label":"Farthest from every warehouse","color":"#E69F00","shape":"ring"},{"id":"area-1","label":"Served by warehouse 1","color":"#009E73","shape":"filled"},{"id":"area-2","label":"Served by warehouse 2","color":"#CC79A7","shape":"filled"},{"id":"center","label":"Warehouse","color":"#F0E442","shape":"filled"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"examined","label":"Checked, not closer","color":"#64748B","shape":"dashed"},{"id":"area-1","label":"Road from warehouse 1","color":"#009E73","shape":"thick"},{"id":"area-2","label":"Road from warehouse 2","color":"#CC79A7","shape":"thick"}],"panels":[{"id":"order","title":"Warehouses","kind":"list"},{"id":"queue","title":"Priority queue","kind":"list"},{"id":"dist","title":"Drive time","kind":"table"}]},"steps":[{"say":"No warehouse is open yet, so every drive time starts at ∞.","ops":[{"panel":"dist","set":{"Home":"∞"}},{"panel":"dist","set":{"Bakery":"∞"}},{"panel":"dist","set":{"Bridge":"∞"}},{"panel":"dist","set":{"Park":"∞"}},{"panel":"dist","set":{"Library":"∞"}},{"panel":"dist","set":{"School":"∞"}}]},{"say":"Open warehouse 1 at Home, which is given. A search from it gives every place it reaches a drive time. The search goes on to Bakery and Bridge.","ops":[{"v":"Home","state":"center"},{"panel":"dist","set":{"Home":"0"}},{"panel":"order","list":[{"key":"Home"}]},{"e":["Home","Bakery"],"state":"area-1"},{"v":"Bakery","state":"waiting"},{"panel":"dist","set":{"Bakery":"4"}},{"e":["Home","Bridge"],"state":"area-1"},{"v":"Bridge","state":"waiting"},{"panel":"dist","set":{"Bridge":"3"}},{"panel":"queue","list":[{"key":"Bridge","note":"3"},{"key":"Bakery","note":"4"}]}]},{"say":"Take Bridge from the queue. Warehouse 1 reaches it in 3, and nothing reaches it sooner. The search goes on to Park.","ops":[{"v":"Bridge","state":"current"},{"e":["Bridge","Park"],"state":"area-1"},{"v":"Park","state":"waiting"},{"panel":"dist","set":{"Park":"5"}},{"panel":"queue","list":[{"key":"Bakery","note":"4"},{"key":"Park","note":"5"}]}]},{"say":"Take Bakery from the queue. Warehouse 1 reaches it in 4, and nothing reaches it sooner. Park already has a drive at least as quick.","ops":[{"v":"Bridge","state":"area-1"},{"v":"Bakery","state":"current"},{"e":["Bakery","Park"],"state":"examined"},{"panel":"queue","list":[{"key":"Park","note":"5"}]}]},{"say":"Take Park from the queue. Warehouse 1 reaches it in 5, and nothing reaches it sooner. The search goes on to Library and School.","ops":[{"v":"Bakery","state":"area-1"},{"v":"Park","state":"current"},{"e":["Park","Library"],"state":"area-1"},{"v":"Library","state":"waiting"},{"panel":"dist","set":{"Library":"9"}},{"e":["Park","School"],"state":"area-1"},{"v":"School","state":"waiting"},{"panel":"dist","set":{"School":"12"}},{"panel":"queue","list":[{"key":"Library","note":"9"},{"key":"School","note":"12"}]}]},{"say":"Take Library from the queue. Warehouse 1 reaches it in 9, and nothing reaches it sooner. The search goes on to School.","ops":[{"v":"Park","state":"area-1"},{"v":"Library","state":"current"},{"e":["Park","School"],"state":"examined"},{"e":["Library","School"],"state":"area-1"},{"v":"School","state":"waiting"},{"panel":"dist","set":{"School":"11"}},{"panel":"queue","list":[{"key":"School","note":"11"}]}]},{"say":"Take School from the queue. Warehouse 1 reaches it in 11, and nothing reaches it sooner. It has no neighbor left to check.","ops":[{"v":"Library","state":"area-1"},{"v":"School","state":"current"},{"panel":"queue","list":[]}]},{"say":"Warehouse 1's search is done. The farthest place from every warehouse is School, 11 from warehouse 1, so warehouse 2 opens there next.","ops":[{"v":"School","state":"area-1"},{"v":"School","state":"farthest"}]},{"say":"Open warehouse 2 at School, which was 11 from warehouse 1. A search from it goes on only while it gets closer than the drive a place already has. The search goes on to Library.","ops":[{"e":["Bakery","Park"],"state":"idle"},{"e":["Park","School"],"state":"idle"},{"e":["Library","School"],"state":"idle"},{"v":"School","state":"center"},{"panel":"dist","set":{"School":"0"}},{"panel":"order","list":[{"key":"Home"},{"key":"School"}]},{"e":["Park","Library"],"state":"idle"},{"e":["School","Library"],"state":"area-2"},{"v":"Library","state":"waiting"},{"panel":"dist","set":{"Library":"2"}},{"panel":"queue","list":[{"key":"Library","note":"2"}]}]},{"say":"Take Library from the queue. Warehouse 2 reaches it in 2, closer than 9 from warehouse 1. Park stays with warehouse 1, which is nearer.","ops":[{"v":"Library","state":"current"},{"e":["Library","Park"],"state":"examined"},{"panel":"queue","list":[]}]},{"say":"Warehouse 2's search is done. 1 place moved to it. 2 warehouses are open. The farthest place from every warehouse is Park, 5 from warehouse 1, so the longest drive is 5. Trying all 15 ways to choose 2 places gives a best of 4. Some roads here are one way, so the factor of two isn't guaranteed.","ops":[{"v":"Library","state":"area-2"},{"v":"Park","state":"farthest"}]}],"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":"centers, longest, err := path.KCenter(g, 2, \"Home\")\nif err != nil {\n\treturn err\n}\nfor _, v := range centers {\n\tfmt.Println(v.Label())\n}\nfmt.Println(longest)"}