Click following link to download PDF of shortest path (Dijkstra’s Algorithm) and Knapsack Problem.
Monthly Archives: July 2013
Dijkstra’s Algorithm for Shortest Path Problem – C Program
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 Dijkstra’s Algorithm for Shortest Path Problem.
Implementation
//**************************************************************************
// Implementation of Dijkstra’s Algorithm in C Language (Greedy Method to solve Shortest Path Problem)
//**************************************************************************
#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];
}
}
void main()
{
int n,v,i,j,cost[10][10],dist[10];
clrscr();
printf(“\n***** DIJKSTRA’S ALGORITHM FOR FINDING SHORTEST PATHS TO EACH NODE *****\n”);
printf(“\nEnter the Number of Nodes:”);
scanf(“%d”,&n);
printf(“\nEnter 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(“\nEnter the Source Node:”);
scanf(“%d”,&v);
dij(n,v,cost,dist);
printf(“\n\n***** Shortest Paths to Each Node *****:\n”);
for(i=1;i<=n;i++)
if(i!=v)
printf(“Node %d -> Node %d, cost=%d\n”,v,i,dist[i]);
getch();
}
Prim’s Algorithm – C Program
Introduction
In computer science, Prim’s algorithm is an algorithm that finds a minimal spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in this newly constructed tree is minimized.
Prim’s algorithm is an example of a greedy algorithm. It constructs minimal spanning tree considering vertices of the graph one by one and any one vertex can be chosen as the starting vertex.
Implementation
//**************************************************************************
// Implementation of Prim’s Algorithm in C Language (Greedy Method to solve MST Problem)
//**************************************************************************
#include<stdio.h>
#include<conio.h>
int a,b,u,v,n,i,j,ne=1;
int visited[10]={0},min,mincost=0,cost[10][10];
void main()
{
clrscr();
printf(“\n***** PRIM’S ALGORITHM FOR MINIMUM SPANNING TREE (MST) *****\n”);
printf(“\nEnter the Number of Nodes: “);
scanf(“%d”,&n);
printf(“\nEnter the Adjacency 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]=999;
}
visited[1]=1;
printf(“\n*** FINAL MST ***”);
while(ne<n)
{
for(i=1,min=999;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]<min)
if(visited[i]!=0)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
if(visited[u]==0 || visited[v]==0)
{
printf(“\nEdge %d: (%d,%d) cost:%d”,ne++,a,b,min);
mincost+=min;
visited[b]=1;
}
cost[a][b]=cost[b][a]=999;
}
printf(“\nMinimun Cost= %d”,mincost);
getch();
}
Kruskal’s Algorithm – C Program
Minimum Spanning Tree, Kruskal’s Algorithm
Kruskal’s algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component). This algorithm is based on greedy approach.
Performance
This algorithm needs to sort the edges and uses a disjoint set data structure to keep track which vertex is in which component. We know the best comparison sorting is O(e*lg(e)), i.e. the merge sort or quick sort, where e is the number of edges, and the set operations can be implemented such a way that they are almost constant. The algorithm itself is linear to the number of edges e. So the total complexity can be achieved is O(e*lg(e)). Also note that, e can be max v*v (when it is a complete graph).
Algorithm
Do some study and paper-work before you proceed:
1. the algorithm and analysis
2. another good pseudo-code
3. read in wikipedia
4. text: Fundamentals of Algorithmics (By Brassard & Bretley, PHI Publication)
Implementation
Here is a short and in general implementation in C language.
//**************************************************************************
// Implementation of Kruskal’s Algorithm in C Language (Greedy Method to solve MST Problem)
//**************************************************************************
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int i,j,k,a,b,u,v,n,ne=1;
int min,mincost=0,cost[9][9],parent[9];
int find(int);
int uni(int,int);
void main()
{
clrscr();
printf(“\n***** KRUSKAL’S ALGORITHM FOR MINIMUM SPANNING TREE (MST) *****\n”);
printf(“\nImplementation of Kruskal’s algorithm\n”);
printf(“\nEnter the No. of Vertices\n”);
scanf(“%d”,&n);
printf(“\nEnter the Cost Adjacency 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]=999;
}
}
printf(“\n*** FINAL MST ***”);
printf(“\nThe Edges of Minimum Cost Spanning Tree are\n”);
while(ne<n)
{
for(i=1,min=999;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(cost[i][j]<min)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
}
}
u=find(u);
v=find(v);
if(uni(u,v))
{
printf(“\n%d Edge (%d,%d) = %d”,ne++,a,b,min);
mincost +=min;
}
cost[a][b]=cost[b][a]=999;
}
printf(“\nMinimum Cost = %d\n”,mincost);
getch();
}
int find(int i)
{
while(parent[i])
i=parent[i];
return i;
}
int uni(int i,int j)
{
if(i!=j)
{
parent[j]=i;
return 1;
}
return 0;
}
Greedy Algorithms – Lecture Note
This article has lecture note on Greedy Algorithms e.g. Making change problem, Minimum Spanning Trees (Kruskal’s algorithm & Prim’s Algorithm).
Download PDF from the following link.
The World SJ Blog 