Tuesday, 1 October 2013

News Paper Delivery Boy

//============================================================================
// Name        : newspaperboy.cpp
// Author      : your name
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
/* Each vertex of the graph represents a lane.An edge of the graph gives distance between two adjacent lanes */

#include <iostream>
using namespace std;
struct path
{
  public:
         int length;
         int n;
         int a[10];
         void insert( int u, int v, int w)
         {
             a[n++] = v;
            length = length + w;
         }
         int member( int x);
          void display();
};

int path::member( int x )
{
    for( int i=0; i<n; i++)
        if(a[i] == x)
        return 1;
    return 0;
}

void path::display()
{
   int i;
   cout<<"\n Path length = " << length << " Path :";
   for( i =0; i<n; i++)
    cout<<a[i]<<" ";
}

class graph
{
  int adj[10][10];
  int vn;            //no. of vertices
  public:
         graph(){ vn = 0;}
         void readgraph();
         void findpath(int u);
};
void graph::findpath(int u)
{
  int top1 = -1,top2 = -1,i,v,minimum;
  path stack1[20], stack2[20];  //stack2 store the final path
  path temp, temp1;

  temp.n = 1;
  temp.length = 0;
  temp.a[0] = u;
  stack1[++top1] = temp;
  while( top1 != -1) // as long as stack1 is not empty
  {
     temp = stack1[top1--];
     // for each vertex adjacent to the last vertex of the path
     u = temp.a[temp.n-1];
     for( v=0; v<vn ; v++)
     {
         if( !temp.member(v) && adj[u][v] != 0)
         {
             temp1 = temp;
             temp1.insert(u,v,adj[u][v]);
             if ( temp1.n == vn)
                 stack2[++top2] = temp1;
             else
                 stack1[++top1] = temp1;
         }
     }
   }
   minimum = 999;
   cout<<"\nAll Paths : \n";
   for( i=0; i<=top2; i++)
   {
       if(stack2[i].length < minimum)
        minimum = stack2[i].length;
    stack2[i].display();
   }
   cout<<"\n Minimum Length Path : \n";
   for( i=0; i <= top2; i++)
   {
      if(stack2[i].length == minimum)
          stack2[i].display();
   }
}

void graph::readgraph()
{
   int i,j;
   int n,u,v,w;
   cout<<"\n Enter no. of vertices : ";
   cin>>vn;
   // initialize
   for( i=0; i<vn; i++)
       for( j=0; j<vn; j++)
           adj[i][j] = 0;
   cout<<"\n Enter no. of edges : ";
   cin>>n;
   cout<<"\nEnter each edge as (u v w) : ";
   for( i=0; i<n; i++)
   {
         cout<<"\n Enter the next edge : ";
         cin>>u>>v>>w;
         adj[u][v] = w;
         adj[v][u] = w;
    }
}

int main()
{
    graph g;
    int start;
    g.readgraph();
    cout<<"\n Enter the starting vertex : ";
    cin>>start;
    g.findpath(start);
    return 0;
}

No comments:

Post a Comment