Dijkstra with Parallel edges and self-loop

Question

If I have a weighted undirected Graph with no negative weights, but can contain multiple edges between vertex and self-loops, Can I run Dijkstra algorithm without problem to find the minimum path between a source and a destination or exists a counterexample?

My guess is that there is not problem, but I want to be sure.

Answer 1

It just needs a minor variation. If there are multiple edges directed from u to v and each edge has a different weight, you can either:

1. Pick the weight with least edge for relaxation; or
2. Run relaxation for each edge.

Both of the above will have the same complexity although the constant factors in #2 will have higher values.

In any case you'll need to make sure that you evaluate all edges between u and v before moving to the next adjacent node of u.

Answer 2

You can trivially transform your graph to one without single-edge loops and parallel edges.

With single-edge loops you need to check whether their weight is negative or non-negative. If the weight is negative, there obviously is no shortest path, as you can keep spinning in place and reduce your path length beyond any limit. If however the weight is positive, you can throw that edge away, as no shortest path can go through that edge.

A zero-weight edge would create a similar problem than any zero-weight loop: there will be not one but an infinite number of shortest paths, going through the same loop over and over again. In these cases the sensible thing is again to remove the edge from the graph.

Out of the parallel edges you can throw away all but the one with the lowest weight. The reasoning for this is equally simple: if there was a shortest path going through an edge A that has a parallel edge B with lower weight, you could construct an even shorter path by simply replacing A with B. Therefore no shortest path can go through A.