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

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;
}