Search code examples
algorithmdijkstrashortest-path

Dijkstra with Parallel edges and self-loop

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? graph

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

Solution

  • If you're going to run Dijkstra's algorithm without making any changes to he graph, there's a chance that you'll not get the shortest path between source and destination.

    For example, consider S and O. Now, finding the shortest path really depends on which edge is being being traversed when you want to push O to the queue. If your code picks edge with weight 1, you're fine. But if your code picks the edge with weight 8, then your algorithm is going to give you the wrong answer.

    This means that the algorithm's correctness is now dependent on the order of edges entered in the adjacency list of the source node.