C Program To Implement Dijkstra's Algorithm

Dijkstra's algorithm is a graph search algorithm which is used to find the shortest path from each vertex to every other vertices in the given directed graph.

Input graph:

               +---------------------------->-----------------------------+
               |                                     4                               |
               |                                                                      |                                   
     +-----  1 ----------------<-----------------  2 -------+              |
     |         |                     5                     |         |              |
     |         |                                            |         |              |
10 ^    9   V                                          7 ^         |              |
     |         |                                            |         |              |
     |         |                     8                     |         |              |
     +-----  3 ---------------->-----------------  4--------^-----------+ 
                |                                                      |
                |                                                      | 
                |                                                      |
                |                         6                            |
                +------------------------->-------------------+


Step 1:  Construct the adjacency matrices that displays the cost of the edges and path between vertices.

       1   2   3    4
1 |  ~   ~   9   4  |      |   -     -    13   14 |
2 |  5   ~   ~   ~  |     |  21    -     -      -  |
3 | 10   6   ~   8  |     |  31   32    -     34 |
4 |  ~   7   ~   ~  |     |   -    42    -      -  |

Left matrix(Cost) shows the cost of the edges and the right matrix(Path) shows the path between vertices.

Notations:
"~"                     -  represent no direct path.
edgeCost(X-Y-Z) -  indicates the sum of cost of the edges XY and YZ.
Cost[X][Y]          -  indicates the cost of the edge XY.

The cost of edge 1-3 is 9.  So, the cost value is placed at the 1st row, 3rd column of Cost matrix and the corresponding edge information (13) is placed at the same location in Path matrix. Similarly, we need to update other entries.

Step 2:  Consider Vertex 1 from the given input graph.
There is an indirect path from 2 to 3 via 1.  So, calculate the path cost and update adjacency matrices.
Cost[2] [3] = edgeCost(2-1) + edgeCost(1-3) = 5 + 9 = 14

Similarly, find all possible indirect paths, calculate path cost and update adjacency matrices.

Indirect path available from 2 to 4 via 1.
Cost[2] [4] = edgeCost(2-1) + edgeCost(1-4) = 5 + 4 = 9

Indirect path available from 3 to 3 via 1.
Cost[3] [3] = edgeCost(3-1) + edgeCost(1-3) = 10 + 9 = 19

Indirect path available from 3 to 4 via 1.
Cost[3] [4] = edgeCost(3-1) + edgeCost(1-3) = 10 + 4 = 14

Even though left matrix has the cost for the edge 3-4, we still calculate the edge cost of the indirect path in order to check whether calculated cost is smaller than the existing one.  If so, update the adjacency matrices with the smaller one.  In this case, calculated cost 14 is greater than the existing cost 8 for the edge 3-4.  So, we don't need to update the adjacency matrices for this case.

       1   2   3     4
1 |  ~    ~   9    4  |     |   -      -     13     14   |
2 |  5    ~  14    9  |    |  21     -    213   214   |
3 | 10    6  19   8  |     |  31    32   313    34   |
4 |  ~    7   ~    ~  |     |   -     42       -      -   |

Step 3:  Consider vertex 2 from the input graph.
Cost[3][3] =  edgeCost(3-2) + edgeCost(2-1-3) = 6 + 14 = 20
(Rejected - Existing Value(19) < Calculated Value(20))

Cost[3][4] =  edgeCost(3-2) + edgeCost(2-1-4) = 6 +   9 = 15 (Rejected - 8 < 25)
Cost[4][1] =  edgeCost(4-2) + edgeCost(2-1)    = 7 +   5 = 12 (Selected)
Cost[4][3] =  edgeCost(4-2) + edgeCost(2-1-3) = 7 + 14 =  21 (Selected)
Cost[4][4] =  edgeCost(4-2) + edgeCost(2-1-4) = 7  +  9 = 16  (Selected)

      1    2    3      4
1 |  ~   ~      9     4  |     |   -      -      13       14 |
2 |  5   ~    14     9  |     |  21     -     213     214 |
3 | 10   6   19     8  |     |  31    32    313      34  |
4 | 12   7   21    16  |     | 421   42  4213  4214   |

Step 4: Consider Vertex 3 from the Input Graph.
Cost[1][1] = edgeCost(1-3)    + edgeCost(3,1) = 9 + 10 = 19
Cost[1][2] = edgeCost(1-3)    + edgeCost(3,2) = 9 +  6  = 15
Cost[2][2] = edgeCost(2-1-3) + edgeCost(3-2) = 14 + 6 = 20

       1   2   3    4
1 | 19  15   9    4  |     |131   132      13       14  |
2 |  5   20  14   9  |     |  21  2132    213     214  |
3 | 10   6   19   8  |     |  31     32    313      34   |
4 | 12   7   21  16 |     | 421     42  4213   4214   |

Step 5:  Consider Vertex 4 from the Input graph.
Cost[1][1] = edgeCost(1-4) + edgeCost(4-2-1) = 4 + 12 = 16
Cost[1][2] = edgeCost(1-4) + edgeCost(4-2)    = 4 + 7   = 11
Cost[2][2] = edgeCost(2-1-4) + edgeCost(4-2) = 9 + 7   = 16

       1   2   3    4
1 | 16  11   9    4  |     |1421   142       13      14  |
2 |  5   16  14   9  |     |  21   2142     213     214  |
3 | 10   6   19   8  |     |  31      32     313      34  |
4 | 12   7   21  16 |     | 421      42   4213    4214 |


See Also:
C Program To Implement Dijkstra's Algorithm
C Program To Find Minimum Spanning Tree Using Prim's Algorithm
C Program To Find Minimum Spanning Tree Using Kruskal's Algorithm
C Program To Implement Breath First Search
C Program To Implement Depth First Search

Example Program To Implement Dijkstra's Algorithm(Shortest Path):

---

  #include <stdio.h>
  #include <stdlib.h>

  #define INFINITY 9999

  int main() {
        int vertexCount, **edgeLength, **res;
        int i, j, k;
        printf("Enter the no of vertices:");
        scanf("%d", &vertexCount);
        edgeLength = (int **)calloc(sizeof(int),  vertexCount);
        res = (int **)calloc(sizeof(int), vertexCount);
        for (i = 0; i < vertexCount; i++) {
                edgeLength[i] = (int *)calloc(sizeof(int),  vertexCount);
                res[i] = (int *)calloc(sizeof(int), vertexCount);
        }

        /* Adjacency Matrix to store Cost of the edges */
        for (i = 0; i < vertexCount; i++) {
                for (j = 0; j < vertexCount; j++) {
                        printf("Edge weight %d to %d(0 if no edge):", i + 1, j + 1);
                        scanf("%d", &edgeLength[i][j]);
                        if (edgeLength[i][j] == 0) {
                                res[i][j] = INFINITY;
                        } else {
                                res[i][j] = edgeLength[i][j];
                        }
                }
        }

        printf("Adjacent matrix for edge weights:\n");

        for (i = 0; i < vertexCount; i++) {

                for (j = 0; j < vertexCount; j++) {

                        printf("%3d", edgeLength[i][j]);

                }

                printf("\n");

        }

        /* Calculate shortest path from each vertex to every other vertices */

        for (i = 0; i < vertexCount; i++) {

                for (j = 0; j < vertexCount; j++) {

                        for (k = 0; k < vertexCount; k++) {

                                if (res[j][k] > res[j][i] + res[i][k]) {

                                        res[j][k] = res[j][i] + res[i][k];

                                }

                        }

                }

        }

        printf("\nShortest path between vertices\n");

        for (i = 0; i < vertexCount; i++) {

                for (j = 0; j < vertexCount; j++) {

                        if (res[i][j] == INFINITY)

                                printf("%3d", 0);

                        else

                                printf("%3d", res[i][j]);

                }

                printf("\n");

        }

        return 0;

  }

  Output:(C Program To Find Shortest Path Using Dijkstra's Algorithm)

  jp@jp-VirtualBox:~/$ ./a.out
  Enter the no of vertices:4
  Edge weight 1 to 1(0 if no edge):0
  Edge weight 1 to 2(0 if no edge):0
  Edge weight 1 to 3(0 if no edge):9
  Edge weight 1 to 4(0 if no edge):4
  Edge weight 2 to 1(0 if no edge):5
  Edge weight 2 to 2(0 if no edge):0
  Edge weight 2 to 3(0 if no edge):0
  Edge weight 2 to 4(0 if no edge):0
  Edge weight 3 to 1(0 if no edge):10
  Edge weight 3 to 2(0 if no edge):6
  Edge weight 3 to 3(0 if no edge):0
  Edge weight 3 to 4(0 if no edge):8
  Edge weight 4 to 1(0 if no edge):0
  Edge weight 4 to 2(0 if no edge):7
  Edge weight 4 to 3(0 if no edge):0
  Edge weight 4 to 4(0 if no edge):0

  Adjacent matrix for edge weights:
    0  0  9  4
    5  0  0  0
   10  6  0  8
    0  7  0  0

  Shortest path between vertices
   16 11  9  4
    5 16 14  9
   10  6 19  8
   12  7 21 16