CODEWITHSUNDEEP
algorithmdata-structuresgraph-theorydijkstra
BEWARB
BEWARB

Reputation: 131

Dijkstra's algorithm on a reverse graph

If we reverse a graph G to G' and run Dijkstra's algorithm on G' from a source vertex 't', will this algorithm give shortest path from all vertices to 't' in G. Can someone prove or find counter example?

Upvotes: 1

Views: 3959

Answers (2)

Tarun Aditya
Tarun Aditya

Reputation: 61

Short answer: YES, your statement is correct in a DIRECTED Graph

In an undirected graph G, the reversal, G' would produce the same graph G, and thus, when you find the shortest distance from source vertex s to all other vertices, you are automatically finding the shortest path from all vertices to s since the graph can be traversed in reverse direction (undirected).

In a directed graph, when you find shortest path from s (source) to all other vertices (destinations), you are travelling in a single direction, from source ---> destination_1, from source ---> destination_2, from source ---> destination_3 ...

So, if you reversed all directions in the graph, all your shortest paths will be: to source <--- destination_1, to source <--- destination_2, to source <--- destination_3 ... and note that These paths will NOT be the same as before i.e. when you run Dijkstras on G', the algorithm thinks it is finding shortest path from s to all d's, whereas in reality, since you reversed the directions, the shortest path arrows are actually pointing in reverse direction giving us shortest path from all d's to s and NOT from s to d's.

Graph G:  

       7           +++++  
   //===>===>====>/ D2 /  
  //              +++++  
 //   /--<<---<--/   /|\
s <---         2      | 1 
 \\   \__<<___        |
  \\      9    \      |
   \\           \ +++++  
    \\===>=====>/ D1 /  
          10    +++++  


Graph G':

       7           +++++
   /----<----<---</ D2 /
  /               +++++
 /    //==>>====>==/   ||
s >===       2         || 1
 \    \__>>___         || 
  \      9    \       \||/
   \           \ +++++
    \---<------</ D1 /
          1     +++++

As you can see above, in G, shortest paths from s to d1 is s -> d1 and from s to d2 is s -> d2 (shown in double lines (=, \\, //)).

Upon reversing the directions, but NOT the weights (obviously), we see that the shortest paths from s to d1 is s -> d2 -> d1 and from s to d2 is s -> d2 which is the output of Djikstras algorithm.

If you were to now set the direction to what it was originally, clearly all the chosen paths are actually the shortest paths TO s and NOT from s.

Graph G:

       7           +++++
   /---->---->--->/ D2 /
  /               +++++
 /    //==<<===<==/   /||\
s <===       2         || 1
 \    \__<<___         || 
  \      9    \        ||
   \           \ +++++
    \--->------>/ D1 /
          1     +++++

P.S.: I know that the presentation isn't that great. sorry 'bout it.

Upvotes: 3

Shizhen Li
Shizhen Li

Reputation: 11

First of all, if G is an undirected graph. It would make no difference for the shortest path on the reverse graph.

Second of all, if G is a directed graph and if we take a closer look of Dijkstra’s, it only states choosing shortest edges among neighbors. So i guess it will work too.

Upvotes: 1

Related Questions