我正在寻找一种方法来解决大型稀疏图上的k-中心问题数据来自openstreetmap，我想在城市中放置k个比萨饼配送分支，这样从分支到图形中任何节点的距离都会最小化。
我应该在哪里设立3家比萨饼配送分店，以覆盖整个城市？
问题：图包含大约50000到250000个节点（来自OpenStrutMeta的数据）。
Simplifaction：解决方案不一定是完美的近似就足够了。k小于20几个小时的运行时间是可以的。
我迫不及待地想听听你的想法如何在这么大的现实世界图（道路网）上解决这个问题。
最佳答案
下面的贪心算法是两个近似的情况下，每个道路的行进时间在两个方向上是相同的。（忽视单行道不应过分扭曲出行时间。）
任意选择第一个中心。对于每个后续的中心，选择顶点从现有的中心最远。使用Dijkstra算法的多个源扩展（初始化优先级队列以包含所有现有中心的距离为0），在参数为n＝250000和k＝20的当代硬件上运行的一个很好的实现应该考虑最多一秒钟或两秒。
关于algorithm - 大图中的k中心(道路网络)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/18298526/