algorithm - 如何选择图中最接近所有其他节点的节点？

Question

一群人需要见面。从一个人的房子到聚会的房子有一定的距离。聚会场所可以是任何人的场所。选择什么房子作为聚会场所最合适？我们正在最小化总距离。

我想到了一个天真的解决方案，即您去每个房子并计算每个人到该位置必须行进的距离。

这个问题的最佳解决方案是什么？

Answer 1

选择传入权重总和最小的节点。

O(V^2) 时间复杂度，其中 V 是节点数。

O(1) 内存复杂度。

伪代码:

min_dist = INF
min_node = null
for node in graph: // O(V) loops
    sum = 0
    for neighbor in neighbors(node): // O(V) loops
        sum += dist(node, neighbor)
        if min_dist <= sum:       // small optimization
            break
    if min_dist > sum:
        min_dist = sum
        min_node = node
return min_node