//============================================================================
// 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;
}
// 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