{"id":749,"date":"2024-10-19T13:51:31","date_gmt":"2024-10-19T08:21:31","guid":{"rendered":"https:\/\/codexplained.in\/?p=749"},"modified":"2025-11-24T15:34:41","modified_gmt":"2025-11-24T10:04:41","slug":"find-shortest-path-using-dijkstras-algorithm","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=749","title":{"rendered":"Find Shortest Path using Dijkstra\u2019s Algorithm"},"content":{"rendered":"
\n#include <stdio.h>\n#include <limits.h>\n\n#define V 9  \/\/ Number of vertices in the graph\n\n\/\/ Function to find the vertex with the minimum distance value\nint minDistance(int dist[], int sptSet[]) {\n    int min = INT_MAX, min_index;\n\n    for (int v = 0; v < V; v++) {\n        if (sptSet[v] == 0 && dist[v] <= min) {\n            min = dist[v];\n            min_index = v;\n        }\n    }\n    return min_index;\n}\n\n\/\/ Function to implement Dijkstra's algorithm\nvoid dijkstra(int graph[V][V], int src) {\n    int dist[V];  \/\/ Output array. dist[i] holds the shortest distance from src to i\n    int sptSet[V]; \/\/ Shortest Path Tree Set\n\n    \/\/ Initialize all distances as infinite and sptSet as false\n    for (int i = 0; i < V; i++) {\n        dist[i] = INT_MAX;\n        sptSet[i] = 0;\n    }\n\n    \/\/ Distance from source to itself is always 0\n    dist[src] = 0;\n\n    \/\/ Find the shortest path for all vertices\n    for (int count = 0; count < V - 1; count++) {\n        \/\/ Pick the minimum distance vertex from the set of vertices not yet processed\n        int u = minDistance(dist, sptSet);\n        sptSet[u] = 1; \/\/ Mark the picked vertex as processed\n\n        \/\/ Update dist value of the neighboring vertices of the picked vertex\n        for (int v = 0; v < V; v++) {\n            \/\/ Update dist[v] if and only if it is not in sptSet, there is an edge from u to v,\n            \/\/ and the total weight of path from src to v through u is smaller than the current value of dist[v]\n            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {\n                dist[v] = dist[u] + graph[u][v];\n            }\n        }\n    }\n\n    \/\/ Print the constructed distance array\n    printf("Vertex \\t Distance from Source\\n");\n    for (int i = 0; i < V; i++) {\n        printf("%d \\t %d\\n", i, dist[i]);\n    }\n}\n\nint main() {\n    \/\/ Example graph represented as an adjacency matrix\n    int graph[V][V] = {\n        {0, 4, 0, 0, 0, 0, 0, 8, 0},\n        {4, 0, 8, 0, 0, 0, 0, 11, 0},\n        {0, 8, 0, 7, 0, 4, 0, 0, 2},\n        {0, 0, 7, 0, 9, 14, 0, 0, 0},\n        {0, 0, 0, 9, 0, 10, 0, 0, 0},\n        {0, 0, 4, 14, 10, 0, 2, 0, 0},\n        {0, 0, 0, 0, 0, 2, 0, 1, 6},\n        {8, 11, 0, 0, 0, 0, 1, 0, 7},\n        {0, 0, 2, 0, 0, 0, 6, 7, 0}\n    };\n\n    dijkstra(graph, 0); \/\/ Starting from vertex 0\n\n    return 0;\n}\n\n<\/pre><\/div>\n\n\n
Explanation of the Code<\/h3>\n\n\n\n
    \n
  1. Constants and Variables<\/strong>:\n
      \n
    • We define V<\/code> as the number of vertices in the graph.<\/li>\n\n\n\n
    • The minDistance<\/code> function finds the vertex with the minimum distance that hasn\u2019t been processed yet.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
    • Dijkstra Function<\/strong>:\n
        \n
      • The dijkstra<\/code> function initializes the dist<\/code> array to store the shortest distances and the sptSet<\/code> array to track processed vertices.<\/li>\n\n\n\n
      • The main loop runs until all vertices have been processed. Inside the loop:\n
          \n
        • It selects the vertex with the smallest distance (not yet processed).<\/li>\n\n\n\n
        • Updates the distances of its adjacent vertices.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n
        • Graph Representation<\/strong>:\n
            \n
          • The graph is represented as an adjacency matrix, where graph[i][j]<\/code> holds the weight of the edge from vertex i<\/code> to vertex j<\/code>. A value of 0<\/code> means no edge exists.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
          • Output<\/strong>:\n
              \n
            • The program prints the shortest distance from the starting vertex (in this case, vertex 0) to all other vertices.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n
              Running the Program<\/h3>\n\n\n\n
              To run this program:<\/p>\n\n\n\n
                \n
              1. Copy the code into a C file, say dijkstra.c<\/code>.<\/li>\n\n\n\n
              2. Compile it using a C compiler. For example:<\/li>\n<\/ol>\n\n\n\n
                gcc dijkstra.c -o dijkstra<\/code><\/pre>\n\n\n\n
                Execute the program:<\/p>\n\n\n\n
                .\/dijkstra\n<\/code><\/pre>\n\n\n\n
                Sample Output<\/h3>\n\n\n\n
                When you run the program, you will see output similar to this:<\/p>\n\n\n\n
                Vertex   Distance from Source\n0       0\n1       4\n2       12\n3       19\n4       21\n5       11\n6       9\n7       8\n8       14\n<\/code><\/pre>\n\n\n\n
                Explanation of Output<\/h3>\n\n\n\n
                  \n
                • The output shows the shortest distance from the starting vertex (0) to each vertex in the graph.<\/li>\n\n\n\n
                • For instance, the shortest distance from vertex 0 to vertex 1 is 4, while the distance to vertex 2 is 12, and so on.<\/li>\n<\/ul>\n\n\n\n
                  <\/p>\n