Dijkstra implementation

#1

The implementation shown here only works for undirected graphs. It fails in directed graphs.Eg: (1->2 , weight=2) , (1->3, weight=4) , (3->2,weight=1). Since there are no outgoing edges from 2 this vertex will not be added in the graphs adjacency list , obviously it will be added in the lists of node 1 and node 3 but there will be nothing as node 2. This causes a problem when we initialize the dist (distances) map in the dijkstraSSSP( ) function the distance of 2 will not be initialized to INT_MAX and thus when we iterate over the child or neighbours of 1 in the latter part of the dijkstraSSSP( ) function nodeDist + the edgeLength = 2 and the default value of dist[ 2 ] = 0 which is less than 2 so it will not be updated . So when we print the final distances of each node from the source the distance of 2 is printed as 0 instead of 2. One can check this by running the code with the inputs g.addEdge(1,2,2,false);
g.addEdge(1,3,4,false);
g.addEdge(3,2,1,false);

#2

Instead of using a map you can use an adjacency list and a visited vector to initialise the values of each node to inf.

#3

Yeah that works. One more question.

#4

Also in the implementation we are not maintaining a visited array i.e a finallized array so, this should also update the a already finallized edge if we had a negative weight edge sinse while checking dist[child] (already finallized) will become greater if we found another parent of that child with a negative edge to that child

#5

Eg. g.addEdge(1,2,2,false);
g.addEdge(1,3,4,false);
g.addEdge(3,2,-3,false)
without maintaining a visited array as shown in the implementation

#6

You cannot use dijkstra for negative edges. Use bellman Ford algorithm for that

#7

Yeah bellman Ford is there , i just wanted to know that if we don’t maintain a visited array and we have a graph like (1–>2 , 2) , ( 1–>3,4) and (3—>2 , -3) then it will work. Thank you for the insights though . :grinning:

#8

Yeah it can work. …

#9

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.