Dijkstra's Algorithm in C: Code & Explanation

Dijkstra's Algorithm in C

This code implements Dijkstra's algorithm to find the shortest path from a source vertex to all other vertices in a graph represented as an adjacency matrix. The program reads graph data from an input.txt file and writes the results to an output.txt file.

Code Implementation

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

#define MAX_VERTICES 100

// Function to find the vertex with minimum distance
int minDistance(int dist[], bool visited[], int vertices) {
    int min = INT_MAX, min_index;

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

    return min_index;
}

// Dijkstra's algorithm implementation
void dijkstra(int graph[MAX_VERTICES][MAX_VERTICES], int vertices, int source) {
    int dist[MAX_VERTICES];
    bool visited[MAX_VERTICES];

    // Initialize distances and visited array
    for (int i = 0; i < vertices; i++) {
        dist[i] = INT_MAX;
        visited[i] = false;
    }

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

    // Find shortest path for all vertices
    for (int count = 0; count < vertices - 1; count++) {
        int u = minDistance(dist, visited, vertices);
        visited[u] = true;

        // Update dist value of adjacent vertices
        for (int v = 0; v < vertices; v++)
            if (!visited[v] && graph[u][v] &&
                dist[u] != INT_MAX &&
                dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }

    // Print the distance array
    printf("Vertex \t Distance from Source\n");
    for (int i = 0; i < vertices; i++)
        printf("%d \t %d\n", i, dist[i] == INT_MAX ? -1 : dist[i]);
}

int main() {
    FILE *input, *output;
    int vertices, edges;

    // Open input file
    input = fopen("input.txt", "r");
    if (input == NULL) {
        printf("Error opening input file\n");
        return 1;
    }

    // Read number of vertices and edges
    fscanf(input, "%d %d", &vertices, &edges);

    // Graph represented as adjacency matrix
    int graph[MAX_VERTICES][MAX_VERTICES] = {0};

    // Read edges and weights
    for (int i = 0; i < edges; i++) {
        int u, v, weight;
        fscanf(input, "%d %d %d", &u, &v, &weight);
        graph[u][v] = weight;
    }

    fclose(input);

    // Open output file
    output = fopen("output.txt", "w");
    if (output == NULL) {
        printf("Error opening output file\n");
        return 1;
    }

    printf("Output.txt generated\n");

    // Redirect stdout to output file
    stdout = output;

    // Run Dijkstra from source vertex 0
    dijkstra(graph, vertices, 0);

    fclose(output);
    return 0;
}

Input File Format (input.txt)

The input.txt file should follow this format:

• The first line contains two integers: the number of vertices and the number of edges.
• Each subsequent line represents an edge and contains three integers: source vertex, destination vertex, and the weight of the edge.

Example:

4 5
0 1 10
0 2 5
1 2 2
1 3 1
2 3 4

Output

The program generates an output.txt file containing the shortest distances from the source vertex (vertex 0) to all other vertices. If a vertex is unreachable, the distance is represented as -1.