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 ?
Best Answer
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.