Find all the edges between any two vertex in a directed graph

3
votes

I have an algorithm to find the edges of a directed graph from a vertex u to any other vertex which has a O(|V|+|E|) time complexity (based on DFS). I have to develop an algorithm to find the edges between any two vertex u and v in O(|V||E|).

Do you have any suggestions or hints to achieve this?

If I repeat the DFS-Visit for every vertex, only the first time the vertex are white and the following times the call will do nothing. If I reset the colour before do that, then the algorithm will be O(|V|^2 + |V||E|).

Thanks you so much in advance!

1
algorithmgraphdepth-first-search
I suppose "any to vertex" should be "any two vertices"? – user529758
Yes, it is edited. Thanks @H2CO3! :) – Stratford
Are you looking for the shortest path? The set of all non-cyclic paths? – Michelle

1 Answers

3
votes

Split the problem into sub-problems where you can use your algorithm to achieve the required complexity, as follows:

  • Use DFS on the structure graph (the underlying undirected graph), and find all the connected components in it. Let them be (V1,E1), (V2,E2), ...., (Vk,Ek)
  • For each such component, run your algorithm. It is obvious that there is no bridge between 2 nodes which are in different components.

The complexity will be:
Step 1 is O(V+E) - DFS.
Step 2:

  • We use the algorithm you developed repeated from each node as black box on each component, so on component i the complexity is O(V_i^2 + V_i*E_i)
  • Since in each component i: E_i >= V_i -1 (otherwise it was not connected, a tree has |V|-1 edges), O(ViEi + Vi^2) = O(ViEi).
  • Thus, the complexity of this step is O(V1E1 + V2E2 + ... + VkEk).

  • Note that for each i E_i <= E, and thus the complexity is not worse then:

    O(V1E + V2E + ... + VkE)  = O(E *(V1+V2+ ... + Vk)) = O(VE)

Thus, the total complexity is O(VE), as required.