Dijsktra's algorithm to compute the shortest path

Input Graph:

Source Code:

File Name: dijsktras.c

#include<stdio.h>

#define INFINITY 9999
#define MAX 10

// Function declaration
void dijkstra(int graph[MAX][MAX], int numVertices, int startNode);

int main() {
    int graph[MAX][MAX], numVertices, i, j, startNode;

    // Input number of vertices
    printf("Enter the number of vertices: ");
    scanf("%d", &numVertices);

    // Input adjacency matrix
    printf("\nEnter the adjacency matrix:\n");
    for (i = 0; i < numVertices; i++) {
        for (j = 0; j < numVertices; j++) {
            scanf("%d", &graph[i][j]);
        }
    }

    // Input the starting node
    printf("\nEnter the starting node (0 to %d): ", numVertices - 1);
    scanf("%d", &startNode);

    // Run Dijkstra's algorithm
    dijkstra(graph, numVertices, startNode);

    return 0;
}

// Dijkstra's algorithm implementation
void dijkstra(int graph[MAX][MAX], int numVertices, int startNode) {
    int cost[MAX][MAX];
    int distance[MAX];        // Shortest distances from startNode
    int predecessor[MAX];     // To store the shortest path tree
    int visited[MAX];         // To mark visited nodes

    int count, minDistance, nextNode, i, j;

    // Create cost matrix (replace 0 with INFINITY, except on diagonal)
    for (i = 0; i < numVertices; i++) {
        for (j = 0; j < numVertices; j++) {
            if (graph[i][j] == 0 && i != j)
                cost[i][j] = INFINITY;
            else
                cost[i][j] = graph[i][j];
        }
    }

    // Initialize distances, predecessors, and visited array
    for (i = 0; i < numVertices; i++) {
        distance[i] = cost[startNode][i];
        predecessor[i] = startNode;
        visited[i] = 0;
    }

    distance[startNode] = 0;
    visited[startNode] = 1;
    count = 1;

    // Find shortest path for all vertices
    while (count < numVertices - 1) {
        minDistance = INFINITY;

        // Find the next node with the smallest tentative distance
        for (i = 0; i < numVertices; i++) {
            if (!visited[i] && distance[i] < minDistance) {
                minDistance = distance[i];
                nextNode = i;
            }
        }

        visited[nextNode] = 1;

        // Update distances of neighboring unvisited nodes
        for (i = 0; i < numVertices; i++) {
            if (!visited[i] && (minDistance + cost[nextNode][i] < distance[i])) {
                distance[i] = minDistance + cost[nextNode][i];
                predecessor[i] = nextNode;
            }
        }

        count++;
    }

    // Print the shortest distance and path from startNode to each other node
    for (i = 0; i < numVertices; i++) {
        if (i != startNode) {
            printf("\nDistance from node %d to node %d = %d", startNode, i, distance[i]);
            printf("\nPath: %d", i);

            j = i;
            while (j != startNode) {
                j = predecessor[j];
                printf(" <- %d", j);
            }
            printf("\n");
        }
    }
}

Output:

$ gcc dijsktras.c
$ ./a.out
Enter the number of vertices: 5

Enter the adjacency matrix:
0 2 0 6 0
2 0 3 8 5
0 3 0 0 7
6 8 0 0 9
0 5 7 9 0

Enter the starting node (0 to 4): 0

Distance from node 0 to node 1 = 2
Path: 1 <- 0

Distance from node 0 to node 2 = 5
Path: 2 <- 1 <- 0

Distance from node 0 to node 3 = 6
Path: 3 <- 0

Distance from node 0 to node 4 = 7
Path: 4 <- 1 <- 0