C Program To Implement Dijkstra's Algorithm For Finding Shortest Path

C Program To Implement Dijkstra's Algorithm For Finding Shortest Path | C Programming

#include "stdio.h"

#include "conio.h"

#define infinity 999

void dij(int n, int v, int cost[10][10], int dist[])

{

    int i, u, count, w, flag[10], min;

    for (i = 1; i <= n; i++)

        flag[i] = 0, dist[i] = cost[v][i];

    count = 2;

    while (count <= n)

    {

        min = 99;

        for (w = 1; w <= n; w++)

            if (dist[w] < min && !flag[w])

                min = dist[w], u = w;

        flag[u] = 1;

        count++;

        for (w = 1; w <= n; w++)

            if ((dist[u] + cost[u][w] < dist[w]) && !flag[w])

                dist[w] = dist[u] + cost[u][w];
    }
}

int main()

{

    int n, v, i, j, cost[10][10], dist[10];

    printf("Enter the number of nodes:");

    scanf("%d", &n);

    printf("\n Enter the cost matrix:\n");

    for (i = 1; i <= n; i++)

        for (j = 1; j <= n; j++)

        {

            scanf("%d", &cost[i][j]);

            if (cost[i][j] == 0)

                cost[i][j] = infinity;
        }

    printf("\n Enter the source matrix:");

    scanf("%d", &v);

    dij(n, v, cost, dist);

    printf("\n Shortest path:n");

    for (i = 1; i <= n; i++)

        if (i != v)

            printf("%d->%d,cost=%dn", v, i, dist[i]);

    return 0;
}