Implementation of Dijkstra's algorithm(Finding shortest path) using C language

C Program to implement Dijkstra's algorithm. Dijkstra's Algorithm finds the shortest path with the lower cost in a Graph. Dijkstra's Algorithm solves the Single Source Shortest Path problem for a Graph. It is a Greedy algorithm and similar to Prim's algorithm. Read more about C Programming Language .

/***********************************************************

* You can use all the programs on  www.engineercse.blogspot.com

* for personal and learning purposes. For permissions to use the

* programs for commercial purposes,

* contact sm.rumi18@gmail.com

* To find more C programs, do visit www.engineercse.blogspot.com

* and browse!

*

*                       Coding is Poetry !!!

***********************************************************/

#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=dist[w],u=w;

  flag[u]=1;

  count++;

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

   if((dist[u]+cost[u][w]

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

 }

}

void main()

{

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

 clrscr();

 printf("\n 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=%d\n",v,i,dist[i]);

 getch();

}

Read more Similar C Programs

Data Structures

Learn C Programming

To get regular updates on new C programs, Algorithm problem solution,

Implementation of Kruskal's Algorithm using C language

C Program to implement Dijkstra's algorithm. Dijkstra's Algorithm finds the shortest path with the lower cost in a Graph. Dijkstra's Algorithm solves the Single Source Shortest Path problem for a Graph. It is a Greedy algorithm and similar to Prim's algorithm. Read more about C Programming Language .

/***********************************************************

* You can use all the programs on  www.engineercse.blogspot.com

* for personal and learning purposes. For permissions to use the

* programs for commercial purposes,

* contact sm.rumi18@gmail.com

* To find more C programs, do visit www.engineercse.blogspot.com

* and browse!

*

*                       Coding fun

***********************************************************/

#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=dist[w],u=w;

  flag[u]=1;

  count++;

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

   if((dist[u]+cost[u][w]

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

 }

}

void main()

{

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

 clrscr();

 printf("\n 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=%d\n",v,i,dist[i]);

 getch();

}

Read more Similar C Programs

Data Structures

Prims Algorithm

Learn C Programming

Implementation of DFS using C program

C program to implement Depth First Search(DFS). Depth First Search is an algorithm used to search the Tree or Graph. DFS search starts from root node then traversal into left child node and continues, if item found it stops other wise it continues. The advantage of DFS is it requires less memory compare to Breadth First Search(BFS). Read more about C Programming Language .

*                    Happy Coding
***********************************************************/

#include
#include
int a[20][20],reach[20],n;
void dfs(int v)
{
 int i;
 reach[v]=1;
 for(i=1;i<=n;i++)
  if(a[v][i] && !reach[i])
  {
   printf("\n %d->%d",v,i);
   dfs(i);
  }
}
void main()
{
 int i,j,count=0;
 clrscr();
 printf("\n Enter number of vertices:");
 scanf("%d",&n);
 for(i=1;i<=n;i++)
 {
  reach[i]=0;
  for(j=1;j<=n;j++)
   a[i][j]=0;
 }
 printf("\n Enter the adjacency matrix:\n");
 for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
   scanf("%d",&a[i][j]);
 dfs(1);
 printf("\n");
 for(i=1;i<=n;i++)
 {
  if(reach[i])
   count++;
 }
 if(count==n)
  printf("\n Graph is connected");
 else
  printf("\n Graph is not connected");
 getch();

}