Can anyone implement Dijkstra’s Algorithm in C++?
I searched on the web but can’t find any easy to understand implementation of the same.
You should surely see Michal Forisek’s answer here : https://www.quora.com/What-is-the-most-simple-efficient-C++-code-for-Dijkstras-shortest-path-algorithm
It works on C++ 11 and it’s one of the simplest and shortest code I have ever seen. Easy to understand too!
You can modify the algorithm to output the shortest distance for each vertex from s rather than a single target vertex. The parameter which is a vector of vectors of type edge, in it the ith position represents a vector of directed edges all of whose tail is i. Other parameters and rest of the code is easy to understand I guess. If you have any doubt feel free to ask me
EDIT: Here’s the complete code with comments (works on C++ 11 or later) which takes input as a graph and outputs the shortest distance from source to all other nodes. The graph I used here was taken from https://www.codechef.com/IOIPRAC/problems/INOI1402 ( You can see the graph there ).
Dijkstra’s Complete code and taking graph as input
His code on compilation shows error also it is not complete.
Are you sure you’re using c++ 11 or else the code shows compilation error!