C Program to Implement Dijkstra’s Algorithm

1. Introduction

Dijkstra's algorithm is a classic graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge paths, producing the shortest path tree. This algorithm is often used in network routing protocols.

2. Program Overview

In this program, we will:

1. Implement the Dijkstra's algorithm using adjacency matrix representation.

2. Find the shortest path from a source vertex to all vertices in the given graph.

3. Code Program

#include <stdio.h>
#include <stdbool.h>
#define INF 99999
#define V 5  // Number of vertices

// A function to find the vertex with the minimum distance value, from the set of vertices not yet included in shortest path tree
int minDistance(int dist[], bool sptSet[]) {
    int min = INF, min_index;

    for (int v = 0; v < V; v++)
        if (sptSet[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;

    return min_index;
}

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

// Dijkstra's algorithm for adjacency matrix representation of the graph
void dijkstra(int graph[V][V], int src) {
    int dist[V];  // The output array. dist[i] will hold the shortest distance from src to i
    bool sptSet[V];  // sptSet[i] will be true if vertex i is included in shortest path tree

    // Initialize all distances as INFINITE and sptSet[] as false
    for (int i = 0; i < V; i++)
        dist[i] = INF, sptSet[i] = false;

    dist[src] = 0;

    // Find shortest path for all vertices
    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;
        for (int v = 0; v < V; v++)
            if (!sptSet[v] && graph[u][v] && dist[u] != INF && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }

    printSolution(dist);
}

// Driver code
int main() {
    int graph[V][V] = {{0, 9, 6, 5, 3},
                       {9, 0, 0, 0, 0},
                       {6, 0, 0, 0, 0},
                       {5, 0, 0, 0, 0},
                       {3, 0, 0, 0, 0}};

    dijkstra(graph, 0);
    return 0;
}

Output:

Vertex 		 Distance from Source
0 		 0
1 		 9
2 		 6
3 		 5
4 		 3

4. Step By Step Explanation

1. minDistance function returns the vertex with the minimum distance value, from the vertices that are not yet included in the shortest path tree.

2. printSolution function is a utility that prints the constructed distance array.

3. In the dijkstra function:

- We initialize the distance of every vertex as infinite (INF).

- We mark the source vertex distance as 0 and proceed to explore its neighbors.

- The main loop runs |V|-1 times (|V| is the number of vertices).

- In each iteration, it selects the vertex that is not in the shortest path tree and has the minimum distance from the source.

- For every adjacent vertex v, if the sum of the distance of u (the selected vertex) from the source and weight u-v, is less than the distance of v from the source, then update the distance of v.

4. In the main function, we define an example graph in the form of an adjacency matrix and then run the dijkstra function.

The algorithm repeatedly selects the next closest vertex and explores all its neighbors. It terminates once all the vertices have been included in the shortest path tree or when the smallest distance in the priority queue is infinity, indicating disconnected nodes in the graph.