How to find all nodes in a graph equidistant from a given set of nodes?

Question

If you have a simple undirected graph G(V,E) and F , which is a subset of V How can you find node V so that the distance from each node from F to V same and the distances are minimized? And just return None if not V I was told that this can be done in complexity O(|V|+|E|) .

Suppose all edges have a distance of 1.

Can someone explain how this can be done? Pseudocode will also help.

Answer 1

The solution is similar to BFS, but with a slight change:

• Start with S = F with the marked F-nodes.

• Find | S | sets with a distance of 1 from each element in S (all these sets must contain unmarked nodes). If the intersection of these sets is nonempty, a candidate will be found.

• Take a union | S | sets higher in S 'and marks these nodes. If S 'is empty, return' None '.

• Return to step 2.

Suppose that all given operations take constant time, then the complexity of the algorithm is the same as BFS, which is O (| V | + | E |).

Now consider the complexity of the given operations. My reasoning is that dialing operations do not increase complexity, since the union and intersection operations in steps 2 and 3 can be combined to take the time O (| S |), and since at each step S differs from S in previous iterations, the total complexity of the given operations will be equal to O (| V |).

Answer 2

Here is one algorithm in pseudo code trying to add comments to explain how this works.

 declare explored // a table of all the vertices that can keep track of one number (distance, initialized to -1) and a list of vertex references (origins, initialized to null) to_explore = S // fifo queue of vertices to explore while (to_explore not empty) { pop vertex v from to_explore current_distance = explored[v].distance current_origins = explored[v].origins for (vertex n, neighbor of v) { if (explored[n].origins contains v) continue // we just hit a loop and we're only interested in shortest distances if (explored[n].distance == -1) { // first time we come here explored[n].distance = current_distance+1 explored[n].origins = current_origins push n to to_explore continue } if (explored[n].distance != current_distance+1) { continue // we are merging path from another node of S but different distance, cannot lead to any solution } // only case left is explored[n].distance == current_distance+1 // so we've already come here from other place(s) in S with the same distance add / merge (without duplicates) origins to explored[n].origins if (explored[n].origins = S) // maybe compare the size is enough? return n // we found a solution // if not , we just continue our exploration, no need to add to the queue since we've already been through here before } } 

The idea is that with the FIFO queue, we will investigate everything that is at a distance of 1 from the set S, if we do not find any solution there, everything is at a distance of 2 ... etc., so we will find the shortest distance first.

I'm not quite sure of the difficulty, but I think that in the worst case, we only examine each vertex and each edge only once to give O(|E| + |V|) . But in some cases, we visit the same peak several times. Although this does not increase the paths to study, I am not sure if there should be a factor | S | somewhere (but if it just counts as a constant, then that's fine ...)

I hope I haven’t missed anything. Obviously, I have not tested any of this .... :)

EDIT (response to comment)

Will your code work for such a graph? E = (a, b), (a, c), (a, d), (b, e), (c, e), (d, e) and my F = {b, c, d}. Say you start bfs with a. I suspect that at the end the source array will have {a} and so the code will return None. - Guru Devanal

In this case, this is what happens:

 to_explore is initialized to {b,c,d} //while (to_explore not empty) pop one from to_explore (b). to_explore becomes {c,d} current_distance=0 current_origins={b} //for (neighbors of b) { handling 'a' as neighbor of b first explored[a].distance=1 explored[a].origins={b} to_explore becomes {c,d,a} //for (neighbors of b) handling 'e' as next neighbor of b explored[e].distance=1 explored[e].origins={b} to_explore becomes {c,d,a,e} //while (to_explore not empty) pop one from to_explore (c). to_explore becomes {d,a,e} current_distance=0 current_origins={c} //for (neighbors of c) handling 'a' as neighbor of c first explored[a].distance is already 1 explored[a].origins={b,c} to_explore already contains a //for (neighbors of c) { handling 'e' as next neighbor of b explored[e].distance is already 1 explored[e].origins={b,} to_explore already contains e //while (to_explore not empty) pop one from to_explore (d) current_distance=0 current_origins={d} //for (neighbors of d) handling 'a' as neighbor of d first explored[a].distance is already 1 explored[a].origins={b,c,d} that matches F, found a as a solution.