1
$\begingroup$

I am wondering why can't Dijkstra's algorithm be applied as it is for undirected graphs. I mean instead of adding 2 directed edges to make it equivalent to a directed graph , why wouldn't it work if this algorithm is applied as it is for undirected graphs ?

So, if that is the case , then can someone please give some example of an undirected graph where applying Dijkstra's algorithm as it is will give a wrong answer ?

EDIT : All edge weights are non-negative. I know i can solve Dijkstra's algorithm for undirected graph by replacing edge by 2 equivalent directed edges. What i am asking is why can't i apply the algorithm as it is without replacing each edge ?

EDIT2 : OK , i may be making some huge mistake. But here is what i have in mind. I keep a heap of vertices with each element of heap representing the distance of that vertex from the source vertex found till now. At each step , i pull the min from the heap and say that the distance of this vertex is actually the shortest lenght path of this vertex from the source vertex. Now i iterate over its neighbours and check if their distances can be updated. If they can be just update them in the heap .

Now what i don't see if how is the directions of edges any relevant in this algorithm ? I just apply the same thing if i have an undirected graph.

Can someone please correct me if i doing some huge mistake on my part ?

$\endgroup$
  • $\begingroup$ It can be applied to undirected graphs by hand, but if you have written a program which works with directed graphs you have to add 2 directed edges. $\endgroup$ – pointer Aug 23 '14 at 7:04
  • 1
    $\begingroup$ As long as all the weights are positive, there is no problem with an undirected graph. Simply replicate each edge in both directions (thus making the graph directed) before you execute the algorithm. $\endgroup$ – barak manos Aug 23 '14 at 7:09
  • $\begingroup$ @barakmanos , check the edits $\endgroup$ – wholesaleLion Aug 23 '14 at 8:16
  • $\begingroup$ How do check if there is an edge from a vertex to another vertex? $\endgroup$ – Tunococ Aug 23 '14 at 8:18
  • $\begingroup$ @Tunococ , assume a adjacency list representation $\endgroup$ – wholesaleLion Aug 23 '14 at 8:20
1
$\begingroup$

Dijkstra's algorithm works just fine for undirected graphs. As others have pointed out, if you are calling a library function that expects a directed graph, then you must duplicate each edge; but if you are writing your own code to do it, you can work with the undirected graph directly.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.