0


Heloo!
i m again sending my code with few more modifications.
please tel me how to find the shortest path between undirected countries.
thanks.

#include<iostream>
#include<fstream>
#include <string>


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);

		// inserting the only node
		if(start == NULL)
		{
			start = end = ptr;
		}
		// inserting node at the front
		else if(s.compare(start->country) == -1)
		{
			ptr->next = start;
			start->prev = ptr;
			start = ptr;
		}
		// inserting at end
		else if(s.compare(end->country) > -1)
		{
			end->next = ptr;
			ptr->prev = end;
			end = ptr;
		}
		// inserting node in the center
		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 printscr()
	{
		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;
			
		}
	}

void print()
{
	
		char *c;
		string hi;
		cout<<"Enter the destination address : ";
		cin>>hi;
		Node *t = start;
		
		while(t != NULL)
		{
		
			c = t->country.begin();
			if(c==hi)
			{
			cout<<"\tCountry:\t\t"<<c<<endl;
			cout<<"\tDistance:\t\t"<<t->dist<<endl;
			break;
			}
			else
			{
			t = t->next;
			}

		}
			if(c!=hi)
			{
			cout<<"No path exist between the source and destination"<<endl;
			}
	
}


};


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);

			// inserting the only node
			if(first == NULL)
			{
				first = last = ptr;
			}

			// inserting node at the front
			else if(s.compare(first->country) == -1)
			{
				ptr->next = first;
				first->prev = ptr;
				first = ptr;
			}

				// inserting at end
			else if(s.compare(last->country) > -1)
			{
				last->next = ptr;
				ptr->prev = last;
				last = ptr;
			}


				// inserting node in the center
			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 printscr()
	{
		node *t = first;
		while(t != NULL)
		{
			char *c;
			c = t->country.begin();
			cout<<"Country:\t\t"<<c<<endl;
			t->printscr();
			cout<<endl;
			t = t->next;
		}
	}

	~list()
	{
	}



/*	void search()
	{

		string hello;
		cout<<"enter source ";
		cin>>hello;
		node *t = first;

		while(t!= NULL)
		{ 	
			char *c;
			c = t->country.begin();
			
			if(c == hello)
			{
				cout<<"country found  : "<< c;
				exit(0);
			}
			else
			{
			t = t->next;
			}
		}
		cout<<"country not found";

	}*/

	void shortt()
	{
		char *c;
		node *t = first;
		string hello;

		cout<<"Enter the source address : ";
		cin>>hello;
		cout<<endl;

		

			while(t!= NULL)
		{ 	
			
			c = t->country.begin();
			
			
			if(c == hello)
			{
				cout<<"Country found  : "<< c<<endl;
				t->print();
				break;
				
			}
			else
			{
			t = t->next;
			}
		}
			if(c!=hello)
			{
			cout<<"Country does not exist on the map"<<endl<<endl;
			}


	}

	void main()
	{
	
		cout<<" 1- Find the shortest path between different countries "<<endl;
		cout<<" 2- Print the directly connected countries "<<endl;
		cout<<" 3- Exit "<<endl;
	}



};

int main()
{
	list l;
	l.build();
	int x;
	char m;

		cout<<endl<<endl<<endl;
		cout<<"			SHORTEST - PATH - DETECTOR	"<<endl<<endl<<endl<<endl;
	while(1)
	{
		l.main();
		cout<<endl<<endl;
		cout<<"Enter the option no. which you wants to do :  ";
		cin>>x;
		if(x==1)
		{
		
		do{	
		l.shortt();
		cout<<"Do u want to continue <y/n> ";
		cin>>m;
		cout<<endl<<endl;
		}while(m!='n');

		
		}

		if(x==2)
		{
		l.printscr();
		}

		if(x==3)
		{
		exit (1);
		}
	}



	return 0;
}
2
Contributors
1
Reply
2
Views
9 Years
Discussion Span
Last Post by VernonDozier
0

You're going to have to be more specific. What's an undirected country? I assume you mean an undirected graph? What's the data look like? Do you have a bunch of latitude and longitude coordinates and country names? Are you given a bunch of countries that are "connected"? Are you given the exact distance between two countries or do you need to calculate it? Do you understand the algorithms involved and just need help coding or do you need help with the algorithms too?

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.