Labels

Thursday 25 June 2015

NEWSPAPER BOY FINDING SHORTEST PATH USING PRIMS ALGORITHM CODE Program

#include<iostream.h> 
#include<conio.h> 
class newspaper{ 
public: 
    int houses; 
    int dist[10][10],visited[10]; 
    void setpath(); 
    void dfs(int); 
    void prims(int[10][10],int); 

}; 

void newspaper::setpath(){ 
int i,j; 
cout<<"Enter no of houses"; 
cin>>houses; 
cout<<"Now enter the distance between them..if no route place 999"; 
for(i=1;i<=houses;i++){ 
    for(j=1;j<=houses;j++){ 
        cout<<"Enter distance between house"<<i<<"to house"<<j; 
        cin>>dist[i][j]; 
        if(dist[i][j]==0)dist[i][j]=999; 
        } 
    } 
for(i=1;i<=houses;i++){ 
        visited[i]=0; 
        } 

void newspaper::dfs(int k){ 
int i; 
cout<<k; 
visited[k]=1; 
for(i=1;i<=houses;i++){ 
    if(dist[i][k]!=0||dist[i][k]!=-99){ 
    if(!visited[i]) 
    dfs(i); 



void newspaper::prims(int dist[10][10],int n){ 
 int visited[10]={0}; 
 int ne,i,j,a,b,u,v=1; 
 int minwt,min=0; 
 visited[1]=1; 
  while(ne<n) 
 { 
  for(i=1,min=999;i<=n;i++) 
   for(j=1;j<=n;j++) 
    if(dist[i][j]<min) 
     if(visited[i]!=0) 
     { 
      min=dist[i][j]; 
      a=u=i; 
      b=v=j; 
     } 
  if(visited[u]==0 || visited[v]==0) 
  { 
   cout<<"\n Edge "<<ne++<<"\t"<<a<<"-"<<b<<"\t"<<min; 
   minwt+=min; 
   visited[b]=1; 
  } 
  dist[a][b]=dist[b][a]=999; 
 } 
 cout<<"\n Minimun cost"<<minwt; 

void main(){ 
newspaper np;int k; 
clrscr(); 
np.setpath(); 
cout<<"Enter the name of house from where to traverse the newspaper"; 
cin>>k; 
cout<<"\n"; 
cout<<"*********Path as per DFS*********"<<"\n"; 
np.dfs(k); 
cout<<"\n"; 
cout<<"******************Shortest Path********"<<"\n"; 
np.prims(np.dist,np.houses); 
getch(); 
}