Dijkstra algorithm to find the shortest path (greedy approach)

Consider having some cities, and a salesman wants to travel from one town (source) to another city (destination) with minimum travel distance.

Here in the below example, we have six cities with travel distances between some of them.

Graph with 6 nodes and path between 1 to 4 with shortest path is 1 –> 2 –> 4.

Below is the Dijkstra’s shortest path algorithm, which is a greedy method.

  1. Initialize distance from the source to every other node as infinite and source to itself as 0.
  2. Get a minimum distance node in all unvisited nodes from the source.
  3. Calculate the total distance of all its corresponding edge nodes and update the array if the distance sum of source node to the minimum node and minimum node to all its edge nodes is minimum then update the distance.
    1. For example., the current distance between 1 and 4 is Infinite. When we calculate it through 2, then the gap will become 5+15, which is 20. So, we update the distance infinite with the new minimum distance 20.
  4. We keep doing the above two steps until there is no unvisited node.
  5. Finally, the result shortest distances from the source node to all other nodes are stored.

Let’s see the code for this algorithm.

    void dijkstra(Vertex v, int paths[]) {
        bool visited[size];
        for(int i=0; i<size; i++) {
            paths[i] = INT_MAX;
            visited[i] = false;
        }

        paths[v.data-1] = 0;

        for(int i=0; i<size; i++) {
            int min = minDistanceVert(paths, visited);

            visited[min] = true;
            for(int j=0; j<size; j++) {
                if(!visited[j] && adjMatrix[min][j] > 0 &&
                    paths[min] != INT_MAX && paths[min] + adjMatrix[min][j] < paths[j]) {
                    paths[j] = paths[min] + adjMatrix[min][j];
                }
            }
        }
    }

The complexity of this algorithm is O(V*E), where V is the number of vertices, and E is the number of edges in the graph.

Please see the below gist for complete code with main function.

Shortest distance from v1 to other nodes: 
0
5
11
20
23
13

It is all about Dijkstra’s shortest path greedy algorithm. If you know any improvements in this code, please let our readers know by commenting here below. Happy Learning!.

See more:
http://rjp.b44.myftpupload.com/topological-sort-of-an-acyclic-directed-graph/
http://rjp.b44.myftpupload.com/breadth-first-search-or-traversal-bfs-of-a-graph/