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$
7
  • $\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$ Commented Aug 23, 2014 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$ Commented Aug 23, 2014 at 7:09
  • $\begingroup$ @barakmanos , check the edits $\endgroup$ Commented Aug 23, 2014 at 8:16
  • $\begingroup$ How do check if there is an edge from a vertex to another vertex? $\endgroup$ Commented Aug 23, 2014 at 8:18
  • $\begingroup$ @Tunococ , assume a adjacency list representation $\endgroup$ Commented Aug 23, 2014 at 8:20

1 Answer 1

Reset to default
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$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.