C Program to implement Dijkstra’s algorithm.

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.c-program-example.com* for personal and learning purposes. For permissions to use the* programs for commercial purposes,* contact [email protected]* To find more C programs, do visit www.c-program-example.com* and browse!* *                      Happy Coding***********************************************************/#include "stdio.h"#include "conio.h"#define infinity 999void 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]; }}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=%dn",v,i,dist[i]); getch();}`
`Read more Similar C ProgramsData StructuresPrims AlgorithmLearn C Programming`

You can easily select the code by double clicking on the code area above.

You can discuss these programs on our Facebook Page. Start a discussion right now,

our page!

(you can send this program to your friend using this button)

(c) www.c-program-example.com

C Program to solve Knapsack problem

C Program to solve Knapsack problem. Knapsack problem is also called as rucksack problem. In Knapsack problem, given a set items with values and weights and a limited weight bag . We have to find the optimum solution so that, in minimum cost(value) fill the bag with the maximum weight. Read more about C Programming Language .

`/************************************************************ You can use all the programs on  www.c-program-example.com* for personal and learning purposes. For permissions to use the* programs for commercial purposes,* contact [email protected]* To find more C programs, do visit www.c-program-example.com* and browse!* *                      Happy Coding***********************************************************/#include<stdio.h>#include<conio.h>int w[10],p[10],v[10][10],n,i,j,cap,x[10]={0};int max(int i,int j){ return ((i>j)?i:j);}int knap(int i,int j){ int value; if(v[i][j]<0) {  if(j<w[i])   value=knap(i-1,j);  else   value=max(knap(i-1,j),p[i]+knap(i-1,j-w[i]));  v[i][j]=value; } return(v[i][j]);}void main(){ int profit,count=0; clrscr(); printf("nEnter the number of elementsn"); scanf("%d",&n); printf("Enter the profit and weights of the elementsn"); for(i=1;i<=n;i++) {  printf("For item no %dn",i);  scanf("%d%d",&p[i],&w[i]); } printf("nEnter the capacity n"); scanf("%d",&cap); for(i=0;i<=n;i++)  for(j=0;j<=cap;j++)   if((i==0)||(j==0))    v[i][j]=0;   else    v[i][j]=-1; profit=knap(n,cap); i=n; j=cap; while(j!=0&&i!=0) {  if(v[i][j]!=v[i-1][j])  {   x[i]=1;   j=j-w[i];   i--;  }  else   i--; } printf("Items included aren"); printf("Sl.notweighttprofitn"); for(i=1;i<=n;i++)  if(x[i])   printf("%dt%dt%dn",++count,w[i],p[i]); printf("Total profit = %dn",profit); getch();}`
`Read more Similar C ProgramsData StructuresLearn C Programming`

You can easily select the code by double clicking on the code area above.