Hello!!
I wanted to know that does anybody can provide me the source code of :
how to find the shortest path between different countries.?
I m sending u my code its in Visual C++ 6.0
I m doing it with adjacency list.
done with adjaceny list but dont know how to find the shortest path.
#include<iostream>
#include<fstream>
#include<cstdlib>
#include<cstdio>
#include<conio.h>
#include<cstring>
using namespace std;
class Node
{
friend class list;
friend class node;
private:
string country;
int dist;
Node *next, *prev;
public:
Node()
{
}
Node(string c, int d)
{
country.assign(c);
dist = d;
prev = next = NULL;
}
~Node()
{
}
};
class node
{
friend class list;
private:
string country;
node *next, *prev;
Node *start, *end;
public:
node()
{
}
node(string s)
{
country.assign(s);
prev = next = NULL;
start = end = NULL;
}
void insert(string s, int d)
{
Node *ptr = new Node(s, d);
if(start == NULL)
{
start = end = ptr;
}
else if(s.compare(start->country) == -1)
{
ptr->next = start;
start->prev = ptr;
start = ptr;
}
else if(s.compare(end->country) > -1)
{
end->next = ptr;
ptr->prev = end;
end = ptr;
}
else
{
Node *temp = start;
while((s.compare(temp->next->country) > -1) && (temp->next != NULL))
{
temp = temp->next;
}
ptr->next = temp->next;
temp->next->prev = ptr;
temp->next = ptr;
ptr->prev = temp;
if(temp == end)
{
end = ptr;
}
}
}
void print()
{
Node *t = start;
while(t != NULL)
{
char *c;
c = t->country.begin();
cout<<"\tCountry:\t\t"<<c<<endl;
cout<<"\tDistance:\t\t"<<t->dist<<endl;
t = t->next;
}
}
};
class list
{
private:
node *first, *last;
public:
list()
{
first = last = NULL;
}
void build()
{
ifstream in("paths.txt", ios::in);
string s;
int d, t;
while(!in.eof())
{
char ch[100];
in>>ch;
s.assign(ch);
node *ptr = new node(s);
if(first == NULL)
{
first = last = ptr;
}
else if(s.compare(first->country) == -1)
{
ptr->next = first;
first->prev = ptr;
first = ptr;
}
else if(s.compare(last->country) > -1)
{
last->next = ptr;
ptr->prev = last;
last = ptr;
}
else
{
node *temp = first;
while((s.compare(temp->next->country) > -1) && (temp->next != NULL))
{
temp = temp->next;
}
ptr->next = temp->next;
temp->next->prev = ptr;
temp->next = ptr;
ptr->prev = temp;
if(temp == last)
{
last = ptr;
}
}
in>>t;
for(int i = 0; i < t; i++)
{
in>>ch;
s.assign(ch);
in>>d;
ptr->insert(s, d);
}
}
}
void print()
{
node *t = first;
while(t != NULL)
{
char *c;
c = t->country.begin();
cout<<"Country:\t\t"<<c<<endl;
t->print();
cout<<endl;
t = t->next;
}
}
~list()
{
}
};
int main()
{
list l;
l.build();
l.print();
return 0;
}