CODEWITHSUNDEEP
algorithmgraph-theoryshortest-path
hakunami
hakunami

Reputation: 2441

Finding a desired point in a connected graph

There is problem, I reduce it to a question as below:

In a connected undirected graph, edge weight is the time to go from one end to another. some people stand on some vertex. Now, they want to meet together, find a place(vertice) that within certain time T, all the people will arrive this assembly point. Try to minimise this T.

More information if you need for margin cases: No negative edge; cycle may exist; More than one person can stay on the same vertice; vertice may have no person; undirected edge, weight measures both u->v or v->u; people start from their initial location;

How to efficiently find it? Should I for every node v, calculate max(SPD(ui, v)) where ui are other people's locations, then choose the minimum one among these max times? Is there a better way?

Upvotes: 1

Views: 79

Answers (2)

Codor
Codor

Reputation: 17605

I believe it could be done within a polynomial runtime bound as follows. In a first pass solve the All-Pairs Shortest Path problem to obtain a matrix with corresponding lengths of shortest paths for all vertices; afterwards iterate over the rows (or columns) and select a column where the maximum entry of all indices on which users are located.

Upvotes: 1

Ante
Ante

Reputation: 5448

It can be done by making parallel Dijkstra from all vertices, and stopping when sets of visited nodes intersect in one node. Intersection can be checked by counting. Algorithm sketch:

node_count = [1, 1, ...] * number_of_nodes  # Number of visited sets node is in
dijkstras = set of objects D_n performing Dijsktra's algorithm starting from node n
queue = priority queue that stores tuples (first_in_queue_n, D_n).
        first_in_queue_n is next node that will be visited by D_n
        initialized by D_n.first_in_queue()
while:
  first_in_queue_n, D_n = queue.pop_min()
  node_count[first_in_queue_n] += 1
  if node_count[first_in_queue_n] == number_of_nodes:
    return first_in_queue_n
  D_n.visite_node(first_in_queue_n)
  queue.add( D_n.first_in_queue() )

Upvotes: 0

Related Questions