Как выбрать узел, ближайший ко всем другим узлам в графе?

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