找到最大权重的子图
koz*_*zyr 5 algorithm graph-theory cluster-analysis subgraph graph-algorithm
我有一个城市区域（让我们将其视为街道图），其中所有街道都有一些与之相关的权重和长度。我想要做的是找到一组连接的街道，位于其他街道附近，具有最大（或接近最大）总权重 W，因为我的最大子图最多只能包含 N 个街道。
我特别对跨越整个图表的子图不感兴趣，而只对一小群具有最大或接近最大组合权重的街道感兴趣，并且所有街道都彼此“靠近”，其中“附近”将定义为距离集群中心不超过 X 米的街道。生成的子图必须连接起来。
有谁知道这个算法的名称是否存在（假设它存在）？
也对任何解决方案感兴趣，无论是精确的还是近似的。
为了直观地显示这一点，假设我的图表是下图中的所有街道路段（十字路口到十字路口）。因此，个别街道不是 A 大道，而是 10 号和 11 号之间的 A 大道，依此类推。街道的权重为 1 或 0。假设权重最大的街道集位于选定的多边形中 - 我想要做的是找到该多边形。
这是一个建议。将节点图中的每个顶点视为您定义的“中心”。对于每个中心C[i]，执行Dijkstra 算法，构造一棵以C[i]为原点的最短路径树。当树包含的顶点数量超过中心允许的最大值时，停止构建树。
然后令A[i]为与以 为中心的树中的顶点相关的所有边的集合V[i]。结果将是A[i]具有最大权重的集合。
Dijkstra 算法执行一次的运行时间是O(|E[i]| + |V[i]| log |V[i]|)针对i第 个中心的。这里的集合的大小受到距中心的最大距离的限制。总成本为sum_(i in 1..|V|) O(|E[i]| + |V[i]| log |V[i]|)。在退化情况下，最大允许权重允许从每个中心包含整个图，成本将为O(|V| (|E| + |V| log |V|))。
我可以想到一些可能的优化来改善运行时间，但想验证这是否能解决您想到的问题。