Dijkstra’s and Multistage Graph Algorithms in C

Posted on Feb 22, 2025 in Communication

Dijkstra’s Algorithm Implementation in C

This code implements Dijkstra’s algorithm to find the shortest path between vertices in a graph. It takes an adjacency matrix as input, where each cell arr[i][j] represents the weight of the edge between vertex i and vertex j. If there is no edge, the value is 0.

#include <stdio.h>

int n; // Global variable for the number of vertices

void insertvalue(int arr[n][n]) {
    int i, j, val, value;

    for (i = 0; i < n; i++) {
        for (j = i; j < n; j++) {
            printf("Enter whether edge is present between vertices %d -- %d (1 - yes, 0 - no): ", i, j);
            scanf("%d", &val);

            if (val == 1) {
                printf("Enter edge value: ");
                scanf("%d", &value);
                arr[i][j] = value;
                arr[j][i] = value; // The graph is undirected
            } else {
                arr[i][j] = 0;
                arr[j][i] = 0;
            }
        }
    }

    // Print the adjacency matrix
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            printf("%d ", arr[i][j]);
        }
        printf("\n");
    }
}


int minvalue(int value[], int visited[]) {
    int min = 999; // Initialize min with a large value
    int vertex;
    int i;

    for (i = 0; i < n; i++) {
        if (visited[i] == 0 && value[i] < min) {
            min = value[i];
            vertex = i;
        }
    }
    return vertex;
}


void djikstra(int arr[n][n]) {
    int i, j;
    int value[n];    // Stores the shortest distance from the source to each vertex
    int parent[n];   // Stores the parent of each vertex in the shortest path tree
    int visited[n];  // Keeps track of visited vertices

    // Initialize arrays
    for (i = 0; i < n; i++) {
        value[i] = 999;
        parent[i] = -1;
        visited[i] = 0;
    }

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

    for (i = 0; i < n - 1; i++) {
        int u = minvalue(value, visited);
        visited[u] = 1;

        for (j = 0; j < n; j++) {
            if (arr[u][j] != 0 && visited[j] == 0 && value[u] != 999 && (value[u] + arr[u][j]) < value[j]) {
                value[j] = value[u] + arr[u][j];
                parent[j] = u;
            }
        }
    }

    // Print the shortest distances
    for (i = 0; i < n; i++) {
        printf("Distance %d -- %d = %d\n", parent[i], i, value[i]);
    }
}

int main() {
    printf("Enter the number of vertices: ");
    scanf("%d", &n);
    int arr[n][n];
    insertvalue(arr);
    djikstra(arr);
    return 0;
}

Multistage Graph Algorithm in C++

This C++ code finds the shortest path in a multistage graph using dynamic programming. The graph is represented by an adjacency matrix adj_mat, where adj_mat[i][j] is the cost to go from vertex i to vertex j. A value of -1 indicates that there is no edge between the vertices.

#include <iostream>
using namespace std;

void multistageGraph(int n, int adj_mat[][100], int d[], int cost[]) {
    cost[n - 1] = 0; // Cost of the last vertex is 0

    for (int i = n - 2; i >= 0; i--) {
        cost[i] = 9999; // Initialize cost to a large value
        for (int j = i; j < n; j++) {
            if (adj_mat[i][j] != -1 && cost[j] + adj_mat[i][j] < cost[i]) {
                cost[i] = cost[j] + adj_mat[i][j];
                d[i] = j; // Store the next vertex in the shortest path
            }
        }
    }
}

int main() {
    int n;
    cout << "Enter the number of vertices: ";
    cin >> n;

    int adj_mat[100][100];
    int cost[100];
    int d[100];
    int path[100];

    cout << "Enter the adjacency matrix for the graph:" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << "Enter the distance from vertex " << i + 1 << " to vertex " << j + 1 << ": ";
            cin >> adj_mat[i][j];
        }
    }

    multistageGraph(n, adj_mat, d, cost);

    // Reconstruct the path
    path[0] = 0;
    int k = 0;
    for (int i = 1; i < n; i++) {
        path[i] = d[path[i - 1]];
        k++;
        if (d[path[i - 1]] == n - 1) {
            break;
        }
    }

    cout << "Path taken: ";
    for (int m = 0; m < k; m++) {
        cout << path[m] + 1 << "--";
    }
    cout << n << endl;

    return 0;
}