CODEWITHSUNDEEP
algorithmoptimizationgraphpuzzle
user2871354
user2871354

Reputation: 550

How to choose node closest to all other nodes in a graph?

Set of people need to meet. There exists a certain distance going from a person's house to the meetup house. The meetup house can be any person's house. What is the optimal house to choose as the meetup house? We are minimizing the total distance.

I thought of the naive solution where you go to each house and take the distance that each person has to travel to that location.

What would be the optimal solution for this problem?

Upvotes: 2

Views: 1602

Answers (1)

Adam Stelmaszczyk
Adam Stelmaszczyk

Reputation: 19857

Choose the node with the lowest sum of incoming weights.

O(V^2) time complexity, where V is the number of nodes.

O(1) memory complexity.

Pseudocode:

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

Upvotes: 4

Related Questions