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

Comments

Post a Comment

Subscribe Us and Thanks for visiting blog.

Popular posts from this blog

C Program for SCAN Disk Scheduling Algorithm | C Programming

Image
Introduction to SCAN disk scheduling :                    In the SCAN algorithm, the disk arm starts at one end of the disk and moves toward the other end, servicing requests as it reaches each cylinder, until it gets to the other end of the disk. At the other end, the direction of the head movement is reversed, and servicing continues. The head continuously scans back and forth across the disk. The SCAN algorithm is sometimes called the elevator algorithm, since the disk arm behaves just like an elevator in a building, first servicing all the requests going up and then reversing to service requests the other way.
Read more

C program to Find Cartesian Product of Two Sets | C programming

Image
C program to find the Cartesian Product of two sets   Cartesian product  is a mathematical operation that returns a set (or  product set  or simply  product ) from multiple sets. That is, for sets  A  and  B , the Cartesian product  A  ×  B  is the set of all ordered pairs  ( a ,  b )  where  a  ∈  A  and  b  ∈  B . Products can be specified using set-builder notation, e.g. {\displaystyle A\times B=\{\,(a,b)\mid a\in A\ {\mbox{ and }}\ b\in B\,\}.}
Read more

C Program To Check The String Is Valid Identifier Or Not | C Programming

Image
C Program To Check The String Is Valid Identifier Or Not #include <stdio.h> #include <conio.h> #include <string.h> int main () { char string [ 25 ]; int count= 0 ,flag; printf ( "Enter any string: " ); gets (string); if ( ( string [ 0 ]>= 'a' && string [ 0 ]<= 'z' )||( string [ 0 ]>= 'A' && string [ 0 ]<= 'Z' )||( string [ 0 ]== '_' )) {     for ( int i= 1 ;i<= strlen (string);i++)     {         if (( string [i]>= 'a' && string [i]<= 'z' )||( string [i]>= 'A' && string [i]<= 'Z' )||( string [i]>= '0' && string [i]<= '9' )||( string [i]== '-' ))     {     count++;     }        }     if (count== strlen (string))     {       flag= 0 ;     } } else {     flag= 1 ; } if (flag== 1 )     printf ( " %s is not valid identifier" ,string); else     printf ( " %s is valid ident
Read more