Does "standard" Dijkstra's algorithm work with bi-directional edges and zero cost edges?

Question

I have been reading about Dijkstra's algorithm and I think I understand it. I followed the algorithm in pseudo-code from Wikipedia, and now I wonder:

If my graph is bi-directional and I add each edge to my graph twice (once "forwards", once "backwards"), will the "standard" Dijkstra's algorithm work?
Is it ok that some of my edges are zero cost? (the rest are all positive - none are negative)

And finally, what is a Dijkstra "heap" algorithm? Is it the same as Dijkstra's algorithm using a PriorityQueue?

I was wondering because I read a description of Dijkstra's referring to "non-negative costs" and I didnt know if this meant "non-zero" also. — vikingsteve, Feb 4, 2014 at 9:10
By "path", I assume you mean "edge"? (A path is a sequence of edges.) "Non-negative" means exactly what it says, bearing in mind that zero is neither positive nor negative. Dijkstra works equally for directed and undirected graphs, so bidirectional edges are not a problem. — David Richerby, Feb 4, 2014 at 9:30

Alexey Romanov · Accepted Answer · 2014-02-04 09:02:46Z

2

Yes, both of these cases work. You can even have zero-cost loops.

answered Feb 4, 2014 at 9:02

Alexey Romanov

3,10716 silver badges20 bronze badges

$\begingroup$ Thanks. Any comment on what the "Dijkstra's heap" is ? $\endgroup$
– vikingsteve
Feb 4, 2014 at 9:10
1

$\begingroup$ I haven't seen this name before. I'd guess this was Dijkstra's algorithm using a heap as a priority queue (note that PQs can be implemented without using heaps, and that there are a few different related data structures called heaps, some of which are useful for Dijkstra's algorithm). $\endgroup$
– Alexey Romanov
Feb 4, 2014 at 9:59

Add a comment |

1 Answer 1