{"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":"downtown-grid","name":"Downtown grid","description":"Twenty intersections on a downtown street grid. Streets go both ways, Market is closed to cars between 2nd and 3rd, and each edge is the travel time in minutes.","family":"road","directed":true,"weighted":true,"acyclic":false,"vertices":[{"id":"Pine & 1st","x":76,"y":156},{"id":"Pine & 2nd","x":283,"y":188},{"id":"Pine & 3rd","x":496,"y":189},{"id":"Pine & 4th","x":706,"y":160},{"id":"Pine & 5th","x":931,"y":161},{"id":"Main & 1st","x":68,"y":383},{"id":"Main & 2nd","x":268,"y":404},{"id":"Main & 3rd","x":518,"y":374},{"id":"Main & 4th","x":739,"y":393},{"id":"Main & 5th","x":946,"y":381},{"id":"Market & 1st","x":73,"y":597},{"id":"Market & 2nd","x":276,"y":620},{"id":"Market & 3rd","x":512,"y":609},{"id":"Market & 4th","x":704,"y":593},{"id":"Market & 5th","x":958,"y":591},{"id":"River & 1st","x":53,"y":842},{"id":"River & 2nd","x":274,"y":833},{"id":"River & 3rd","x":489,"y":826},{"id":"River & 4th","x":701,"y":833},{"id":"River & 5th","x":950,"y":829}],"edges":[{"from":"Pine & 1st","to":"Pine & 2nd","weight":2},{"from":"Pine & 2nd","to":"Pine & 1st","weight":2},{"from":"Pine & 1st","to":"Main & 1st","weight":2},{"from":"Main & 1st","to":"Pine & 1st","weight":2},{"from":"Pine & 2nd","to":"Pine & 3rd","weight":3},{"from":"Pine & 3rd","to":"Pine & 2nd","weight":3},{"from":"Pine & 2nd","to":"Main & 2nd","weight":3},{"from":"Main & 2nd","to":"Pine & 2nd","weight":3},{"from":"Pine & 3rd","to":"Pine & 4th","weight":2},{"from":"Pine & 4th","to":"Pine & 3rd","weight":2},{"from":"Pine & 3rd","to":"Main & 3rd","weight":2},{"from":"Main & 3rd","to":"Pine & 3rd","weight":2},{"from":"Pine & 4th","to":"Pine & 5th","weight":3},{"from":"Pine & 5th","to":"Pine & 4th","weight":3},{"from":"Pine & 4th","to":"Main & 4th","weight":2},{"from":"Main & 4th","to":"Pine & 4th","weight":2},{"from":"Pine & 5th","to":"Main & 5th","weight":3},{"from":"Main & 5th","to":"Pine & 5th","weight":3},{"from":"Main & 1st","to":"Main & 2nd","weight":3},{"from":"Main & 2nd","to":"Main & 1st","weight":3},{"from":"Main & 1st","to":"Market & 1st","weight":3},{"from":"Market & 1st","to":"Main & 1st","weight":3},{"from":"Main & 2nd","to":"Main & 3rd","weight":4},{"from":"Main & 3rd","to":"Main & 2nd","weight":4},{"from":"Main & 2nd","to":"Market & 2nd","weight":2},{"from":"Market & 2nd","to":"Main & 2nd","weight":2},{"from":"Main & 3rd","to":"Main & 4th","weight":4},{"from":"Main & 4th","to":"Main & 3rd","weight":4},{"from":"Main & 3rd","to":"Market & 3rd","weight":3},{"from":"Market & 3rd","to":"Main & 3rd","weight":3},{"from":"Main & 4th","to":"Main & 5th","weight":3},{"from":"Main & 5th","to":"Main & 4th","weight":3},{"from":"Main & 4th","to":"Market & 4th","weight":2},{"from":"Market & 4th","to":"Main & 4th","weight":2},{"from":"Main & 5th","to":"Market & 5th","weight":2},{"from":"Market & 5th","to":"Main & 5th","weight":2},{"from":"Market & 1st","to":"Market & 2nd","weight":2},{"from":"Market & 2nd","to":"Market & 1st","weight":2},{"from":"Market & 1st","to":"River & 1st","weight":2},{"from":"River & 1st","to":"Market & 1st","weight":2},{"from":"Market & 2nd","to":"River & 2nd","weight":2},{"from":"River & 2nd","to":"Market & 2nd","weight":2},{"from":"Market & 3rd","to":"Market & 4th","weight":3},{"from":"Market & 4th","to":"Market & 3rd","weight":3},{"from":"Market & 3rd","to":"River & 3rd","weight":3},{"from":"River & 3rd","to":"Market & 3rd","weight":3},{"from":"Market & 4th","to":"Market & 5th","weight":2},{"from":"Market & 5th","to":"Market & 4th","weight":2},{"from":"Market & 4th","to":"River & 4th","weight":3},{"from":"River & 4th","to":"Market & 4th","weight":3},{"from":"Market & 5th","to":"River & 5th","weight":2},{"from":"River & 5th","to":"Market & 5th","weight":2},{"from":"River & 1st","to":"River & 2nd","weight":3},{"from":"River & 2nd","to":"River & 1st","weight":3},{"from":"River & 2nd","to":"River & 3rd","weight":2},{"from":"River & 3rd","to":"River & 2nd","weight":2},{"from":"River & 3rd","to":"River & 4th","weight":2},{"from":"River & 4th","to":"River & 3rd","weight":2},{"from":"River & 4th","to":"River & 5th","weight":4},{"from":"River & 5th","to":"River & 4th","weight":4}],"details":{"vertices":20,"edges":60,"directed":true,"weighted":true,"acyclic":false,"weightMin":2,"weightMax":4,"negativeWeights":false,"density":0.15789473684210525,"inDegree":{"min":2,"avg":3,"max":4},"outDegree":{"min":2,"avg":3,"max":4},"selfLoops":0,"components":1}},"problem":"With one warehouse at Pine & 1st, where should three more open so that the longest drive to any intersection is as short as it can be made, and how close does that come to the best?","params":{"k":4,"sources":["Pine & 1st"]},"result":{"kind":"order","vertices":["Pine \u0026 1st","River \u0026 5th","River \u0026 2nd","Pine \u0026 4th"]},"answer":"Open warehouses at Pine & 1st, River & 5th, River & 2nd and Pine & 4th, in that order. The longest drive is 5. The best of all 4,845 ways to choose 4 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":"area-3","label":"Served by warehouse 3","color":"#56B4E9","shape":"filled"},{"id":"area-4","label":"Served by warehouse 4","color":"#D55E00","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"},{"id":"area-3","label":"Road from warehouse 3","color":"#56B4E9","shape":"thick"},{"id":"area-4","label":"Road from warehouse 4","color":"#D55E00","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":{"Pine & 1st":"∞"}},{"panel":"dist","set":{"Pine & 2nd":"∞"}},{"panel":"dist","set":{"Pine & 3rd":"∞"}},{"panel":"dist","set":{"Pine & 4th":"∞"}},{"panel":"dist","set":{"Pine & 5th":"∞"}},{"panel":"dist","set":{"Main & 1st":"∞"}},{"panel":"dist","set":{"Main & 2nd":"∞"}},{"panel":"dist","set":{"Main & 3rd":"∞"}},{"panel":"dist","set":{"Main & 4th":"∞"}},{"panel":"dist","set":{"Main & 5th":"∞"}},{"panel":"dist","set":{"Market & 1st":"∞"}},{"panel":"dist","set":{"Market & 2nd":"∞"}},{"panel":"dist","set":{"Market & 3rd":"∞"}},{"panel":"dist","set":{"Market & 4th":"∞"}},{"panel":"dist","set":{"Market & 5th":"∞"}},{"panel":"dist","set":{"River & 1st":"∞"}},{"panel":"dist","set":{"River & 2nd":"∞"}},{"panel":"dist","set":{"River & 3rd":"∞"}},{"panel":"dist","set":{"River & 4th":"∞"}},{"panel":"dist","set":{"River & 5th":"∞"}}]},{"say":"Open warehouse 1 at Pine & 1st, which is given. A search from it gives every place it reaches a drive time. The search goes on to Pine & 2nd and Main & 1st.","ops":[{"v":"Pine & 1st","state":"center"},{"panel":"dist","set":{"Pine & 1st":"0"}},{"panel":"order","list":[{"key":"Pine & 1st"}]},{"e":["Pine & 1st","Pine & 2nd"],"state":"area-1"},{"v":"Pine & 2nd","state":"waiting"},{"panel":"dist","set":{"Pine & 2nd":"2"}},{"e":["Pine & 1st","Main & 1st"],"state":"area-1"},{"v":"Main & 1st","state":"waiting"},{"panel":"dist","set":{"Main & 1st":"2"}},{"panel":"queue","list":[{"key":"Pine & 2nd","note":"2"},{"key":"Main & 1st","note":"2"}]}]},{"say":"Take Pine & 2nd from the queue. Warehouse 1 reaches it in 2, and nothing reaches it sooner. The search goes on to Pine & 3rd and Main & 2nd.","ops":[{"v":"Pine & 2nd","state":"current"},{"e":["Pine & 2nd","Pine & 3rd"],"state":"area-1"},{"v":"Pine & 3rd","state":"waiting"},{"panel":"dist","set":{"Pine & 3rd":"5"}},{"e":["Pine & 2nd","Main & 2nd"],"state":"area-1"},{"v":"Main & 2nd","state":"waiting"},{"panel":"dist","set":{"Main & 2nd":"5"}},{"panel":"queue","list":[{"key":"Main & 1st","note":"2"},{"key":"Main & 2nd","note":"5"},{"key":"Pine & 3rd","note":"5"}]}]},{"say":"Take Main & 1st from the queue. Warehouse 1 reaches it in 2, and nothing reaches it sooner. The search goes on to Market & 1st. Main & 2nd already has a drive at least as quick.","ops":[{"v":"Pine & 2nd","state":"area-1"},{"v":"Main & 1st","state":"current"},{"e":["Main & 1st","Main & 2nd"],"state":"examined"},{"e":["Main & 1st","Market & 1st"],"state":"area-1"},{"v":"Market & 1st","state":"waiting"},{"panel":"dist","set":{"Market & 1st":"5"}},{"panel":"queue","list":[{"key":"Main & 2nd","note":"5"},{"key":"Market & 1st","note":"5"},{"key":"Pine & 3rd","note":"5"}]}]},{"say":"Take Main & 2nd from the queue. Warehouse 1 reaches it in 5, and nothing reaches it sooner. The search goes on to Main & 3rd and Market & 2nd.","ops":[{"v":"Main & 1st","state":"area-1"},{"v":"Main & 2nd","state":"current"},{"e":["Main & 2nd","Main & 3rd"],"state":"area-1"},{"v":"Main & 3rd","state":"waiting"},{"panel":"dist","set":{"Main & 3rd":"9"}},{"e":["Main & 2nd","Market & 2nd"],"state":"area-1"},{"v":"Market & 2nd","state":"waiting"},{"panel":"dist","set":{"Market & 2nd":"7"}},{"panel":"queue","list":[{"key":"Market & 1st","note":"5"},{"key":"Pine & 3rd","note":"5"},{"key":"Market & 2nd","note":"7"},{"key":"Main & 3rd","note":"9"}]}]},{"say":"Take Market & 1st from the queue. Warehouse 1 reaches it in 5, and nothing reaches it sooner. The search goes on to River & 1st. Market & 2nd already has a drive at least as quick.","ops":[{"v":"Main & 2nd","state":"area-1"},{"v":"Market & 1st","state":"current"},{"e":["Market & 1st","Market & 2nd"],"state":"examined"},{"e":["Market & 1st","River & 1st"],"state":"area-1"},{"v":"River & 1st","state":"waiting"},{"panel":"dist","set":{"River & 1st":"7"}},{"panel":"queue","list":[{"key":"Pine & 3rd","note":"5"},{"key":"River & 1st","note":"7"},{"key":"Market & 2nd","note":"7"},{"key":"Main & 3rd","note":"9"}]}]},{"say":"Take Pine & 3rd from the queue. Warehouse 1 reaches it in 5, and nothing reaches it sooner. The search goes on to Pine & 4th and Main & 3rd.","ops":[{"v":"Market & 1st","state":"area-1"},{"v":"Pine & 3rd","state":"current"},{"e":["Pine & 3rd","Pine & 4th"],"state":"area-1"},{"v":"Pine & 4th","state":"waiting"},{"panel":"dist","set":{"Pine & 4th":"7"}},{"e":["Main & 2nd","Main & 3rd"],"state":"examined"},{"e":["Pine & 3rd","Main & 3rd"],"state":"area-1"},{"v":"Main & 3rd","state":"waiting"},{"panel":"dist","set":{"Main & 3rd":"7"}},{"panel":"queue","list":[{"key":"River & 1st","note":"7"},{"key":"Main & 3rd","note":"7"},{"key":"Pine & 4th","note":"7"},{"key":"Market & 2nd","note":"7"}]}]},{"say":"Take River & 1st from the queue. Warehouse 1 reaches it in 7, and nothing reaches it sooner. The search goes on to River & 2nd.","ops":[{"v":"Pine & 3rd","state":"area-1"},{"v":"River & 1st","state":"current"},{"e":["River & 1st","River & 2nd"],"state":"area-1"},{"v":"River & 2nd","state":"waiting"},{"panel":"dist","set":{"River & 2nd":"10"}},{"panel":"queue","list":[{"key":"Main & 3rd","note":"7"},{"key":"Market & 2nd","note":"7"},{"key":"Pine & 4th","note":"7"},{"key":"River & 2nd","note":"10"}]}]},{"say":"Take Main & 3rd from the queue. Warehouse 1 reaches it in 7, and nothing reaches it sooner. The search goes on to Main & 4th and Market & 3rd.","ops":[{"v":"River & 1st","state":"area-1"},{"v":"Main & 3rd","state":"current"},{"e":["Main & 3rd","Main & 4th"],"state":"area-1"},{"v":"Main & 4th","state":"waiting"},{"panel":"dist","set":{"Main & 4th":"11"}},{"e":["Main & 3rd","Market & 3rd"],"state":"area-1"},{"v":"Market & 3rd","state":"waiting"},{"panel":"dist","set":{"Market & 3rd":"10"}},{"panel":"queue","list":[{"key":"Market & 2nd","note":"7"},{"key":"Pine & 4th","note":"7"},{"key":"River & 2nd","note":"10"},{"key":"Market & 3rd","note":"10"},{"key":"Main & 4th","note":"11"}]}]},{"say":"Take Market & 2nd from the queue. Warehouse 1 reaches it in 7, and nothing reaches it sooner. The search goes on to River & 2nd.","ops":[{"v":"Main & 3rd","state":"area-1"},{"v":"Market & 2nd","state":"current"},{"e":["River & 1st","River & 2nd"],"state":"examined"},{"e":["Market & 2nd","River & 2nd"],"state":"area-1"},{"v":"River & 2nd","state":"waiting"},{"panel":"dist","set":{"River & 2nd":"9"}},{"panel":"queue","list":[{"key":"Pine & 4th","note":"7"},{"key":"River & 2nd","note":"9"},{"key":"Market & 3rd","note":"10"},{"key":"Main & 4th","note":"11"}]}]},{"say":"Take Pine & 4th from the queue. Warehouse 1 reaches it in 7, and nothing reaches it sooner. The search goes on to Pine & 5th and Main & 4th.","ops":[{"v":"Market & 2nd","state":"area-1"},{"v":"Pine & 4th","state":"current"},{"e":["Pine & 4th","Pine & 5th"],"state":"area-1"},{"v":"Pine & 5th","state":"waiting"},{"panel":"dist","set":{"Pine & 5th":"10"}},{"e":["Main & 3rd","Main & 4th"],"state":"examined"},{"e":["Pine & 4th","Main & 4th"],"state":"area-1"},{"v":"Main & 4th","state":"waiting"},{"panel":"dist","set":{"Main & 4th":"9"}},{"panel":"queue","list":[{"key":"River & 2nd","note":"9"},{"key":"Main & 4th","note":"9"},{"key":"Market & 3rd","note":"10"},{"key":"Pine & 5th","note":"10"}]}]},{"say":"Take River & 2nd from the queue. Warehouse 1 reaches it in 9, and nothing reaches it sooner. The search goes on to River & 3rd.","ops":[{"v":"Pine & 4th","state":"area-1"},{"v":"River & 2nd","state":"current"},{"e":["River & 2nd","River & 3rd"],"state":"area-1"},{"v":"River & 3rd","state":"waiting"},{"panel":"dist","set":{"River & 3rd":"11"}},{"panel":"queue","list":[{"key":"Main & 4th","note":"9"},{"key":"Market & 3rd","note":"10"},{"key":"Pine & 5th","note":"10"},{"key":"River & 3rd","note":"11"}]}]},{"say":"Take Main & 4th from the queue. Warehouse 1 reaches it in 9, and nothing reaches it sooner. The search goes on to Main & 5th and Market & 4th.","ops":[{"v":"River & 2nd","state":"area-1"},{"v":"Main & 4th","state":"current"},{"e":["Main & 4th","Main & 5th"],"state":"area-1"},{"v":"Main & 5th","state":"waiting"},{"panel":"dist","set":{"Main & 5th":"12"}},{"e":["Main & 4th","Market & 4th"],"state":"area-1"},{"v":"Market & 4th","state":"waiting"},{"panel":"dist","set":{"Market & 4th":"11"}},{"panel":"queue","list":[{"key":"Market & 3rd","note":"10"},{"key":"Pine & 5th","note":"10"},{"key":"Market & 4th","note":"11"},{"key":"River & 3rd","note":"11"},{"key":"Main & 5th","note":"12"}]}]},{"say":"Take Market & 3rd from the queue. Warehouse 1 reaches it in 10, and nothing reaches it sooner. Market & 4th and River & 3rd already have a drive at least as quick.","ops":[{"v":"Main & 4th","state":"area-1"},{"v":"Market & 3rd","state":"current"},{"e":["Market & 3rd","Market & 4th"],"state":"examined"},{"e":["Market & 3rd","River & 3rd"],"state":"examined"},{"panel":"queue","list":[{"key":"Pine & 5th","note":"10"},{"key":"Market & 4th","note":"11"},{"key":"River & 3rd","note":"11"},{"key":"Main & 5th","note":"12"}]}]},{"say":"Take Pine & 5th from the queue. Warehouse 1 reaches it in 10, and nothing reaches it sooner. Main & 5th already has a drive at least as quick.","ops":[{"v":"Market & 3rd","state":"area-1"},{"v":"Pine & 5th","state":"current"},{"e":["Pine & 5th","Main & 5th"],"state":"examined"},{"panel":"queue","list":[{"key":"Market & 4th","note":"11"},{"key":"River & 3rd","note":"11"},{"key":"Main & 5th","note":"12"}]}]},{"say":"Take Market & 4th from the queue. Warehouse 1 reaches it in 11, and nothing reaches it sooner. The search goes on to Market & 5th and River & 4th.","ops":[{"v":"Pine & 5th","state":"area-1"},{"v":"Market & 4th","state":"current"},{"e":["Market & 4th","Market & 5th"],"state":"area-1"},{"v":"Market & 5th","state":"waiting"},{"panel":"dist","set":{"Market & 5th":"13"}},{"e":["Market & 4th","River & 4th"],"state":"area-1"},{"v":"River & 4th","state":"waiting"},{"panel":"dist","set":{"River & 4th":"14"}},{"panel":"queue","list":[{"key":"River & 3rd","note":"11"},{"key":"Main & 5th","note":"12"},{"key":"Market & 5th","note":"13"},{"key":"River & 4th","note":"14"}]}]},{"say":"Take River & 3rd from the queue. Warehouse 1 reaches it in 11, and nothing reaches it sooner. The search goes on to River & 4th.","ops":[{"v":"Market & 4th","state":"area-1"},{"v":"River & 3rd","state":"current"},{"e":["Market & 4th","River & 4th"],"state":"examined"},{"e":["River & 3rd","River & 4th"],"state":"area-1"},{"v":"River & 4th","state":"waiting"},{"panel":"dist","set":{"River & 4th":"13"}},{"panel":"queue","list":[{"key":"Main & 5th","note":"12"},{"key":"River & 4th","note":"13"},{"key":"Market & 5th","note":"13"}]}]},{"say":"Take Main & 5th from the queue. Warehouse 1 reaches it in 12, and nothing reaches it sooner. Market & 5th already has a drive at least as quick.","ops":[{"v":"River & 3rd","state":"area-1"},{"v":"Main & 5th","state":"current"},{"e":["Main & 5th","Market & 5th"],"state":"examined"},{"panel":"queue","list":[{"key":"River & 4th","note":"13"},{"key":"Market & 5th","note":"13"}]}]},{"say":"Take River & 4th from the queue. Warehouse 1 reaches it in 13, and nothing reaches it sooner. The search goes on to River & 5th.","ops":[{"v":"Main & 5th","state":"area-1"},{"v":"River & 4th","state":"current"},{"e":["River & 4th","River & 5th"],"state":"area-1"},{"v":"River & 5th","state":"waiting"},{"panel":"dist","set":{"River & 5th":"17"}},{"panel":"queue","list":[{"key":"Market & 5th","note":"13"},{"key":"River & 5th","note":"17"}]}]},{"say":"Take Market & 5th from the queue. Warehouse 1 reaches it in 13, and nothing reaches it sooner. The search goes on to River & 5th.","ops":[{"v":"River & 4th","state":"area-1"},{"v":"Market & 5th","state":"current"},{"e":["River & 4th","River & 5th"],"state":"examined"},{"e":["Market & 5th","River & 5th"],"state":"area-1"},{"v":"River & 5th","state":"waiting"},{"panel":"dist","set":{"River & 5th":"15"}},{"panel":"queue","list":[{"key":"River & 5th","note":"15"}]}]},{"say":"Take River & 5th from the queue. Warehouse 1 reaches it in 15, and nothing reaches it sooner. It has no neighbor left to check.","ops":[{"v":"Market & 5th","state":"area-1"},{"v":"River & 5th","state":"current"},{"panel":"queue","list":[]}]},{"say":"Warehouse 1's search is done. The farthest place from every warehouse is River & 5th, 15 from warehouse 1, so warehouse 2 opens there next.","ops":[{"v":"River & 5th","state":"area-1"},{"v":"River & 5th","state":"farthest"}]},{"say":"Open warehouse 2 at River & 5th, which was 15 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 Market & 5th and River & 4th.","ops":[{"e":["Main & 1st","Main & 2nd"],"state":"idle"},{"e":["Main & 2nd","Main & 3rd"],"state":"idle"},{"e":["Main & 3rd","Main & 4th"],"state":"idle"},{"e":["Main & 5th","Market & 5th"],"state":"idle"},{"e":["Market & 1st","Market & 2nd"],"state":"idle"},{"e":["Market & 3rd","Market & 4th"],"state":"idle"},{"e":["Market & 3rd","River & 3rd"],"state":"idle"},{"e":["Market & 4th","River & 4th"],"state":"idle"},{"e":["Pine & 5th","Main & 5th"],"state":"idle"},{"e":["River & 1st","River & 2nd"],"state":"idle"},{"e":["River & 4th","River & 5th"],"state":"idle"},{"e":["Market & 5th","River & 5th"],"state":"idle"},{"v":"River & 5th","state":"center"},{"panel":"dist","set":{"River & 5th":"0"}},{"panel":"order","list":[{"key":"Pine & 1st"},{"key":"River & 5th"}]},{"e":["Market & 4th","Market & 5th"],"state":"idle"},{"e":["River & 5th","Market & 5th"],"state":"area-2"},{"v":"Market & 5th","state":"waiting"},{"panel":"dist","set":{"Market & 5th":"2"}},{"e":["River & 3rd","River & 4th"],"state":"idle"},{"e":["River & 5th","River & 4th"],"state":"area-2"},{"v":"River & 4th","state":"waiting"},{"panel":"dist","set":{"River & 4th":"4"}},{"panel":"queue","list":[{"key":"Market & 5th","note":"2"},{"key":"River & 4th","note":"4"}]}]},{"say":"Take Market & 5th from the queue. Warehouse 2 reaches it in 2, closer than 13 from warehouse 1. The search goes on to Main & 5th and Market & 4th.","ops":[{"v":"Market & 5th","state":"current"},{"e":["Main & 4th","Main & 5th"],"state":"idle"},{"e":["Market & 5th","Main & 5th"],"state":"area-2"},{"v":"Main & 5th","state":"waiting"},{"panel":"dist","set":{"Main & 5th":"4"}},{"e":["Main & 4th","Market & 4th"],"state":"idle"},{"e":["Market & 5th","Market & 4th"],"state":"area-2"},{"v":"Market & 4th","state":"waiting"},{"panel":"dist","set":{"Market & 4th":"4"}},{"panel":"queue","list":[{"key":"River & 4th","note":"4"},{"key":"Market & 4th","note":"4"},{"key":"Main & 5th","note":"4"}]}]},{"say":"Take River & 4th from the queue. Warehouse 2 reaches it in 4, closer than 13 from warehouse 1. The search goes on to River & 3rd. Market & 4th already has a drive at least as quick.","ops":[{"v":"Market & 5th","state":"area-2"},{"v":"River & 4th","state":"current"},{"e":["River & 4th","Market & 4th"],"state":"examined"},{"e":["River & 2nd","River & 3rd"],"state":"idle"},{"e":["River & 4th","River & 3rd"],"state":"area-2"},{"v":"River & 3rd","state":"waiting"},{"panel":"dist","set":{"River & 3rd":"6"}},{"panel":"queue","list":[{"key":"Market & 4th","note":"4"},{"key":"Main & 5th","note":"4"},{"key":"River & 3rd","note":"6"}]}]},{"say":"Take Market & 4th from the queue. Warehouse 2 reaches it in 4, closer than 11 from warehouse 1. The search goes on to Main & 4th and Market & 3rd.","ops":[{"v":"River & 4th","state":"area-2"},{"v":"Market & 4th","state":"current"},{"e":["Pine & 4th","Main & 4th"],"state":"idle"},{"e":["Market & 4th","Main & 4th"],"state":"area-2"},{"v":"Main & 4th","state":"waiting"},{"panel":"dist","set":{"Main & 4th":"6"}},{"e":["Main & 3rd","Market & 3rd"],"state":"idle"},{"e":["Market & 4th","Market & 3rd"],"state":"area-2"},{"v":"Market & 3rd","state":"waiting"},{"panel":"dist","set":{"Market & 3rd":"7"}},{"panel":"queue","list":[{"key":"Main & 5th","note":"4"},{"key":"River & 3rd","note":"6"},{"key":"Main & 4th","note":"6"},{"key":"Market & 3rd","note":"7"}]}]},{"say":"Take Main & 5th from the queue. Warehouse 2 reaches it in 4, closer than 12 from warehouse 1. The search goes on to Pine & 5th. Main & 4th already has a drive at least as quick.","ops":[{"v":"Market & 4th","state":"area-2"},{"v":"Main & 5th","state":"current"},{"e":["Main & 5th","Main & 4th"],"state":"examined"},{"e":["Pine & 4th","Pine & 5th"],"state":"idle"},{"e":["Main & 5th","Pine & 5th"],"state":"area-2"},{"v":"Pine & 5th","state":"waiting"},{"panel":"dist","set":{"Pine & 5th":"7"}},{"panel":"queue","list":[{"key":"River & 3rd","note":"6"},{"key":"Main & 4th","note":"6"},{"key":"Pine & 5th","note":"7"},{"key":"Market & 3rd","note":"7"}]}]},{"say":"Take River & 3rd from the queue. Warehouse 2 reaches it in 6, closer than 11 from warehouse 1. The search goes on to River & 2nd. Market & 3rd already has a drive at least as quick.","ops":[{"v":"Main & 5th","state":"area-2"},{"v":"River & 3rd","state":"current"},{"e":["River & 3rd","Market & 3rd"],"state":"examined"},{"e":["Market & 2nd","River & 2nd"],"state":"idle"},{"e":["River & 3rd","River & 2nd"],"state":"area-2"},{"v":"River & 2nd","state":"waiting"},{"panel":"dist","set":{"River & 2nd":"8"}},{"panel":"queue","list":[{"key":"Main & 4th","note":"6"},{"key":"Market & 3rd","note":"7"},{"key":"Pine & 5th","note":"7"},{"key":"River & 2nd","note":"8"}]}]},{"say":"Take Main & 4th from the queue. Warehouse 2 reaches it in 6, closer than 9 from warehouse 1. Pine & 4th and Main & 3rd stay with warehouse 1, which is nearer.","ops":[{"v":"River & 3rd","state":"area-2"},{"v":"Main & 4th","state":"current"},{"e":["Main & 4th","Pine & 4th"],"state":"examined"},{"e":["Main & 4th","Main & 3rd"],"state":"examined"},{"panel":"queue","list":[{"key":"Market & 3rd","note":"7"},{"key":"Pine & 5th","note":"7"},{"key":"River & 2nd","note":"8"}]}]},{"say":"Take Market & 3rd from the queue. Warehouse 2 reaches it in 7, closer than 10 from warehouse 1. Main & 3rd stays with warehouse 1, which is nearer.","ops":[{"v":"Main & 4th","state":"area-2"},{"v":"Market & 3rd","state":"current"},{"e":["Market & 3rd","Main & 3rd"],"state":"examined"},{"panel":"queue","list":[{"key":"Pine & 5th","note":"7"},{"key":"River & 2nd","note":"8"}]}]},{"say":"Take Pine & 5th from the queue. Warehouse 2 reaches it in 7, closer than 10 from warehouse 1. Pine & 4th stays with warehouse 1, which is nearer.","ops":[{"v":"Market & 3rd","state":"area-2"},{"v":"Pine & 5th","state":"current"},{"e":["Pine & 5th","Pine & 4th"],"state":"examined"},{"panel":"queue","list":[{"key":"River & 2nd","note":"8"}]}]},{"say":"Take River & 2nd from the queue. Warehouse 2 reaches it in 8, closer than 9 from warehouse 1. Market & 2nd and River & 1st stay with warehouse 1, which is nearer.","ops":[{"v":"Pine & 5th","state":"area-2"},{"v":"River & 2nd","state":"current"},{"e":["River & 2nd","Market & 2nd"],"state":"examined"},{"e":["River & 2nd","River & 1st"],"state":"examined"},{"panel":"queue","list":[]}]},{"say":"Warehouse 2's search is done. 9 places moved to it. The farthest place from every warehouse is River & 2nd, 8 from warehouse 2, so warehouse 3 opens there next.","ops":[{"v":"River & 2nd","state":"area-2"},{"v":"River & 2nd","state":"farthest"}]},{"say":"Open warehouse 3 at River & 2nd, which was 8 from warehouse 2. A search from it goes on only while it gets closer than the drive a place already has. The search goes on to Market & 2nd, River & 1st and River & 3rd.","ops":[{"e":["Main & 4th","Main & 3rd"],"state":"idle"},{"e":["Main & 4th","Pine & 4th"],"state":"idle"},{"e":["Main & 5th","Main & 4th"],"state":"idle"},{"e":["Market & 3rd","Main & 3rd"],"state":"idle"},{"e":["Pine & 5th","Pine & 4th"],"state":"idle"},{"e":["River & 2nd","Market & 2nd"],"state":"idle"},{"e":["River & 2nd","River & 1st"],"state":"idle"},{"e":["River & 3rd","Market & 3rd"],"state":"idle"},{"e":["River & 4th","Market & 4th"],"state":"idle"},{"e":["River & 3rd","River & 2nd"],"state":"idle"},{"v":"River & 2nd","state":"center"},{"panel":"dist","set":{"River & 2nd":"0"}},{"panel":"order","list":[{"key":"Pine & 1st"},{"key":"River & 5th"},{"key":"River & 2nd"}]},{"e":["Main & 2nd","Market & 2nd"],"state":"idle"},{"e":["River & 2nd","Market & 2nd"],"state":"area-3"},{"v":"Market & 2nd","state":"waiting"},{"panel":"dist","set":{"Market & 2nd":"2"}},{"e":["Market & 1st","River & 1st"],"state":"idle"},{"e":["River & 2nd","River & 1st"],"state":"area-3"},{"v":"River & 1st","state":"waiting"},{"panel":"dist","set":{"River & 1st":"3"}},{"e":["River & 4th","River & 3rd"],"state":"idle"},{"e":["River & 2nd","River & 3rd"],"state":"area-3"},{"v":"River & 3rd","state":"waiting"},{"panel":"dist","set":{"River & 3rd":"2"}},{"panel":"queue","list":[{"key":"Market & 2nd","note":"2"},{"key":"River & 3rd","note":"2"},{"key":"River & 1st","note":"3"}]}]},{"say":"Take Market & 2nd from the queue. Warehouse 3 reaches it in 2, closer than 7 from warehouse 1. The search goes on to Main & 2nd and Market & 1st.","ops":[{"v":"Market & 2nd","state":"current"},{"e":["Pine & 2nd","Main & 2nd"],"state":"idle"},{"e":["Market & 2nd","Main & 2nd"],"state":"area-3"},{"v":"Main & 2nd","state":"waiting"},{"panel":"dist","set":{"Main & 2nd":"4"}},{"e":["Main & 1st","Market & 1st"],"state":"idle"},{"e":["Market & 2nd","Market & 1st"],"state":"area-3"},{"v":"Market & 1st","state":"waiting"},{"panel":"dist","set":{"Market & 1st":"4"}},{"panel":"queue","list":[{"key":"River & 3rd","note":"2"},{"key":"River & 1st","note":"3"},{"key":"Main & 2nd","note":"4"},{"key":"Market & 1st","note":"4"}]}]},{"say":"Take River & 3rd from the queue. Warehouse 3 reaches it in 2, closer than 6 from warehouse 2. The search goes on to Market & 3rd. River & 4th stays with warehouse 2, which is at least as near.","ops":[{"v":"Market & 2nd","state":"area-3"},{"v":"River & 3rd","state":"current"},{"e":["River & 3rd","River & 4th"],"state":"examined"},{"e":["Market & 4th","Market & 3rd"],"state":"idle"},{"e":["River & 3rd","Market & 3rd"],"state":"area-3"},{"v":"Market & 3rd","state":"waiting"},{"panel":"dist","set":{"Market & 3rd":"5"}},{"panel":"queue","list":[{"key":"River & 1st","note":"3"},{"key":"Market & 1st","note":"4"},{"key":"Main & 2nd","note":"4"},{"key":"Market & 3rd","note":"5"}]}]},{"say":"Take River & 1st from the queue. Warehouse 3 reaches it in 3, closer than 7 from warehouse 1. Market & 1st already has a drive at least as quick.","ops":[{"v":"River & 3rd","state":"area-3"},{"v":"River & 1st","state":"current"},{"e":["River & 1st","Market & 1st"],"state":"examined"},{"panel":"queue","list":[{"key":"Market & 1st","note":"4"},{"key":"Main & 2nd","note":"4"},{"key":"Market & 3rd","note":"5"}]}]},{"say":"Take Market & 1st from the queue. Warehouse 3 reaches it in 4, closer than 5 from warehouse 1. Main & 1st stays with warehouse 1, which is nearer.","ops":[{"v":"River & 1st","state":"area-3"},{"v":"Market & 1st","state":"current"},{"e":["Market & 1st","Main & 1st"],"state":"examined"},{"panel":"queue","list":[{"key":"Main & 2nd","note":"4"},{"key":"Market & 3rd","note":"5"}]}]},{"say":"Take Main & 2nd from the queue. Warehouse 3 reaches it in 4, closer than 5 from warehouse 1. Pine & 2nd, Main & 1st and Main & 3rd stay with warehouse 1, which is nearer.","ops":[{"v":"Market & 1st","state":"area-3"},{"v":"Main & 2nd","state":"current"},{"e":["Main & 2nd","Pine & 2nd"],"state":"examined"},{"e":["Main & 2nd","Main & 1st"],"state":"examined"},{"e":["Main & 2nd","Main & 3rd"],"state":"examined"},{"panel":"queue","list":[{"key":"Market & 3rd","note":"5"}]}]},{"say":"Take Market & 3rd from the queue. Warehouse 3 reaches it in 5, closer than 7 from warehouse 2. Main & 3rd stays with warehouse 1, which is nearer. Market & 4th stays with warehouse 2, which is nearer.","ops":[{"v":"Main & 2nd","state":"area-3"},{"v":"Market & 3rd","state":"current"},{"e":["Market & 3rd","Main & 3rd"],"state":"examined"},{"e":["Market & 3rd","Market & 4th"],"state":"examined"},{"panel":"queue","list":[]}]},{"say":"Warehouse 3's search is done. 6 places moved to it. The farthest place from every warehouse is Pine & 4th, 7 from warehouse 1, so warehouse 4 opens there next.","ops":[{"v":"Market & 3rd","state":"area-3"},{"v":"Pine & 4th","state":"farthest"}]},{"say":"Open warehouse 4 at Pine & 4th, which was 7 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 Pine & 3rd, Pine & 5th and Main & 4th.","ops":[{"e":["Main & 2nd","Main & 1st"],"state":"idle"},{"e":["Main & 2nd","Main & 3rd"],"state":"idle"},{"e":["Main & 2nd","Pine & 2nd"],"state":"idle"},{"e":["Market & 1st","Main & 1st"],"state":"idle"},{"e":["Market & 3rd","Main & 3rd"],"state":"idle"},{"e":["Market & 3rd","Market & 4th"],"state":"idle"},{"e":["River & 1st","Market & 1st"],"state":"idle"},{"e":["River & 3rd","River & 4th"],"state":"idle"},{"e":["Pine & 3rd","Pine & 4th"],"state":"idle"},{"v":"Pine & 4th","state":"center"},{"panel":"dist","set":{"Pine & 4th":"0"}},{"panel":"order","list":[{"key":"Pine & 1st"},{"key":"River & 5th"},{"key":"River & 2nd"},{"key":"Pine & 4th"}]},{"e":["Pine & 2nd","Pine & 3rd"],"state":"idle"},{"e":["Pine & 4th","Pine & 3rd"],"state":"area-4"},{"v":"Pine & 3rd","state":"waiting"},{"panel":"dist","set":{"Pine & 3rd":"2"}},{"e":["Main & 5th","Pine & 5th"],"state":"idle"},{"e":["Pine & 4th","Pine & 5th"],"state":"area-4"},{"v":"Pine & 5th","state":"waiting"},{"panel":"dist","set":{"Pine & 5th":"3"}},{"e":["Market & 4th","Main & 4th"],"state":"idle"},{"e":["Pine & 4th","Main & 4th"],"state":"area-4"},{"v":"Main & 4th","state":"waiting"},{"panel":"dist","set":{"Main & 4th":"2"}},{"panel":"queue","list":[{"key":"Pine & 3rd","note":"2"},{"key":"Main & 4th","note":"2"},{"key":"Pine & 5th","note":"3"}]}]},{"say":"Take Pine & 3rd from the queue. Warehouse 4 reaches it in 2, closer than 5 from warehouse 1. The search goes on to Main & 3rd. Pine & 2nd stays with warehouse 1, which is nearer.","ops":[{"v":"Pine & 3rd","state":"current"},{"e":["Pine & 3rd","Pine & 2nd"],"state":"examined"},{"e":["Pine & 3rd","Main & 3rd"],"state":"idle"},{"e":["Pine & 3rd","Main & 3rd"],"state":"area-4"},{"v":"Main & 3rd","state":"waiting"},{"panel":"dist","set":{"Main & 3rd":"4"}},{"panel":"queue","list":[{"key":"Main & 4th","note":"2"},{"key":"Pine & 5th","note":"3"},{"key":"Main & 3rd","note":"4"}]}]},{"say":"Take Main & 4th from the queue. Warehouse 4 reaches it in 2, closer than 6 from warehouse 2. Main & 5th and Market & 4th stay with warehouse 2, which is at least as near. Main & 3rd already has a drive at least as quick.","ops":[{"v":"Pine & 3rd","state":"area-4"},{"v":"Main & 4th","state":"current"},{"e":["Main & 4th","Main & 3rd"],"state":"examined"},{"e":["Main & 4th","Main & 5th"],"state":"examined"},{"e":["Main & 4th","Market & 4th"],"state":"examined"},{"panel":"queue","list":[{"key":"Pine & 5th","note":"3"},{"key":"Main & 3rd","note":"4"}]}]},{"say":"Take Pine & 5th from the queue. Warehouse 4 reaches it in 3, closer than 7 from warehouse 2. Main & 5th stays with warehouse 2, which is nearer.","ops":[{"v":"Main & 4th","state":"area-4"},{"v":"Pine & 5th","state":"current"},{"e":["Pine & 5th","Main & 5th"],"state":"examined"},{"panel":"queue","list":[{"key":"Main & 3rd","note":"4"}]}]},{"say":"Take Main & 3rd from the queue. Warehouse 4 reaches it in 4, closer than 7 from warehouse 1. Main & 2nd and Market & 3rd stay with warehouse 3, which is nearer.","ops":[{"v":"Pine & 5th","state":"area-4"},{"v":"Main & 3rd","state":"current"},{"e":["Main & 3rd","Main & 2nd"],"state":"examined"},{"e":["Main & 3rd","Market & 3rd"],"state":"examined"},{"panel":"queue","list":[]}]},{"say":"Warehouse 4's search is done. 4 places moved to it. 4 warehouses are open. The farthest place from every warehouse is Market & 3rd, 5 from warehouse 3, so the longest drive is 5. Trying all 4,845 ways to choose 4 places gives a best of 4. Every road here works both ways in the same time, so this is never worse than twice the best.","ops":[{"v":"Main & 3rd","state":"area-4"},{"v":"Market & 3rd","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, 4, \"Pine & 1st\")\nif err != nil {\n\treturn err\n}\nfor _, v := range centers {\n\tfmt.Println(v.Label())\n}\nfmt.Println(longest)"}