Dijkstra's Algorithm for shortest paths in C

C Program to implement Graph Structure: Exercise-9 with Solution

Write a C program that creates a function to find the shortest path from a source vertex to all other vertices using Dijkstra's algorithm.

From Wikipdeia,

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

The algorithm exists in many variants. Dijkstra's original algorithm found the shortest path between two given nodes, but a more common variant fixes a single node as the "source" node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree.

Visual Presentation:

Dijkstra's algorithm to find the shortest path between a and b. It picks the unvisited vertex with the lowest distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor's distance if smaller.

Source: Wikipdeia

Sample Solution:

C Code:

#include <stdio.h>
#include <limits.h>

#define MAX_VERTICES 100

// Function to find the vertex with the minimum distance value
int minDistance(int dist[], int sptSet[], int vertices) {
    int min = INT_MAX, minIndex;

    for (int v = 0; v < vertices; v++) {
        if (!sptSet[v] && dist[v] < min) {
            min = dist[v];
            minIndex = v;
        }
    }

    return minIndex;
}

// Function to print the constructed distance array
void printSolution(int dist[], int vertices) {
    printf("Vertex \tDistance from Source\n");
    for (int i = 0; i < vertices; i++) {
        printf("%d \t%d\n", i, dist[i]);
    }
}

// Function to implement Dijkstra's algorithm for a given graph and source vertex
void dijkstra(int graph[MAX_VERTICES][MAX_VERTICES], int src, int vertices) {
    int dist[MAX_VERTICES]; // The output array dist[i] holds the shortest distance from src to i
    int sptSet[MAX_VERTICES]; // sptSet[i] will be true if vertex i is included in the shortest path tree or the shortest distance from src to i is finalized

    // Initialize all distances as INFINITE and sptSet[] as false
    for (int i = 0; i < vertices; i++) {
        dist[i] = INT_MAX;
        sptSet[i] = 0;
    }

    // Distance from source vertex to itself is always 0
    dist[src] = 0;

    // Find the shortest path for all vertices
    for (int count = 0; count < vertices - 1; count++) {
        // Pick the minimum distance vertex from the set of vertices not yet processed.
        // u is always equal to src in the first iteration.
        int u = minDistance(dist, sptSet, vertices);

        // Mark the picked vertex as processed
        sptSet[u] = 1;

        // Update dist value of the adjacent vertices of the picked vertex.
        for (int v = 0; v < vertices; v++) {
            // Update dist[v] only if it is not in the sptSet, there is an edge from u to v,
            // and the total weight of path from src to v through u is smaller than the current value of dist[v]
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    // Print the constructed distance array
    printSolution(dist, vertices);
}

int main() {
    int vertices;

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

    if (vertices <= 0 || vertices > MAX_VERTICES) {
        printf("Invalid number of vertices. Exiting...\n");
        return 1;
    }

    int graph[MAX_VERTICES][MAX_VERTICES];

    // Input the adjacency matrix representing the weighted graph
    printf("Input the adjacency matrix for the graph (use INT_MAX for infinity):\n");
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            scanf("%d", &graph[i][j]);
        }
    }

    int source;

    // Input the source vertex
    printf("Input the source vertex: ");
    scanf("%d", &source);

    if (source < 0 || source >= vertices) {
        printf("Invalid source vertex. Exiting...\n");
        return 1;
    }

    // Perform Dijkstra's algorithm
    dijkstra(graph, source, vertices);

    return 0;
}

Output:

Input the number of vertices: 5
Input the adjacency matrix for the graph (use INT_MAX for infinity):
0 3 2 0 0
3 0 0 1 0
2 0 0 1 4
0 1 1 0 2
0 0 4 2 0
Input the source vertex: 0
Vertex  Distance from Source
0       0
1       3
2       2
3       3
4       5 

Explanation:

In the exercise above,

• minDistance Function:
• It finds the vertex with the minimum distance value from the source vertex that has not been processed yet.
• Parameters:
• dist: Array holding the distance values from the source vertex.
• sptSet: Array indicating whether a vertex is included in the shortest path tree.
• vertices: Number of vertices in the graph.
• printSolution Function:
• It prints the constructed distance array.
• Parameters:
• dist: Array holding the distance values from the source vertex.
• vertices: Number of vertices in the graph.
• dijkstra Function:
• It performs Dijkstra's algorithm to find the shortest paths.
• Parameters:
• graph: Adjacency matrix representing the weighted graph.
• src: Source vertex.
• vertices: Number of vertices in the graph.
• It initializes dist with infinite distances and sptSet as false.
• It sets the distance from the source vertex to itself as 0.
• It iterates to find the shortest paths for all vertices.
• Picks the vertex with the minimum distance from the set of vertices not yet processed.
• Marks the picked vertex as processed.
• Updates the distance values of the adjacent vertices of the picked vertex.
• main Function:
• It takes input for the number of vertices, the adjacency matrix, and the source vertex.
• Calls the "dijkstra()" function with the input parameters.

Flowchart:

C Programming Code Editor:

Previous: Prim's Algorithm for minimum Spanning Tree in C.
Next: Binary Tree traversal in C: In-Order, Pre-Order, Post-Order.