#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <fstream>
#include <string>
#include <vector>
#include <sstream>
#include <list>
#include <limits.h>


using namespace std;



class Node
{
public:
	string name;
	vector<string> edges;
	vector<int> dist;
};

class Path
{
public:
	vector <int> distance;
	vector <string> fromwhere;
	vector <int> complete;
	vector <string> cities;
	vector <int> currentdistance;
	vector <string> path;
};

int main ()
{
	int c, i, j, k, num_of_cities, rows, totaldistance;
	num_of_cities = 0;
	totaldistance = 0;
	string line, temp_name, temp_edge, temp_dist, temp_to, temp_from;
	stringstream iss, source_to_dest;
	vector<Node> nodes;
	vector<string> lines, paths;
	ifstream inFile("ukcities.txt");
	Node temp_add;
	i = 0;
	j = 0;
	rows = 0;
	if (inFile)
	{
	while (getline(inFile, line, '\n'))
	{
		lines.push_back(line);
		iss.clear();
		iss << line;		
		getline(iss, temp_name, '\t');
		getline(iss, temp_edge, '\t');
		getline(iss, temp_dist, '\t');
		num_of_cities = nodes.size();
			if (num_of_cities == 0)
			{
				temp_add.name = temp_name;
				temp_add.edges.push_back(temp_edge);
				const char *c_ptr=temp_dist.c_str();
				temp_add.dist.push_back(atoi(c_ptr));
				nodes.push_back(temp_add);
				temp_add.name = temp_edge;
				temp_add.edges.clear();
				temp_add.dist.clear();
				temp_add.edges.push_back(temp_name);
				temp_add.dist.push_back(atoi(c_ptr));
				nodes.push_back(temp_add);
			}
			else 
			{
				i = 0;
				j = 0;
				num_of_cities = nodes.size();
				while (!(i >= num_of_cities) && (j==0))
				{
					if (nodes[i].name == temp_name)
					{
						j = 1;
						const char *c_ptr=temp_dist.c_str();
						nodes[i].dist.push_back(atoi(c_ptr));
						nodes[i].edges.push_back(temp_edge);
						i=0;

						
					}
					else
						i++;
				}
					if (j==0)
					{
						j = 1;
						temp_add.edges.clear();
						temp_add.dist.clear();
						temp_add.name = temp_name;
						temp_add.edges.push_back(temp_edge);
						const char *c_ptr=temp_dist.c_str();
						temp_add.dist.push_back(atoi(c_ptr));
						nodes.push_back(temp_add);
						
						i = 0;
					}
						i = 0;
						j = 0;
						num_of_cities = nodes.size();
						while (!(i >= num_of_cities) && (j==0))
						{
							if (nodes[i].name == temp_edge)
							{
								j = 1;
								temp_add.edges.clear();
								temp_add.dist.clear();
								const char *c_ptr=temp_dist.c_str();
								nodes[i].dist.push_back(atoi(c_ptr));
								nodes[i].edges.push_back(temp_name);
								i=0;
								
							}
							else
								i++;
						}
						if (j==0)
						{
							temp_add.edges.clear();
							temp_add.dist.clear();
							temp_add.name = temp_edge;
							temp_add.edges.push_back(temp_name);
							const char *c_ptr=temp_dist.c_str();
							temp_add.dist.push_back(atoi(c_ptr));
							nodes.push_back(temp_add);
							i=0;
						}
					
				}
			}
		iss.clear();
		
	}
	for (k = 0; k != num_of_cities; k++)
	{

		cout << nodes[k].name << '\n';
	}

	ifstream inPathFile("findpath.txt");
	
	while (getline(inPathFile, line, '\n'))
	{
		int number_of_edges, min, wheremin, count, l, m;
		string prev_citie;
		Path distances;
		Path add_distances;
		vector <string> pathtaken;
		vector <int> pathdistance;
		vector<string>::iterator it;
		number_of_edges = 0;
		wheremin = 0;
		m= 0;
		num_of_cities = nodes.size();
		paths.push_back(line);
		iss.clear();
		iss << line;		
		getline(iss, temp_from, '\t');
		getline(iss, temp_to, '\t');
		cout << "meow" << '\n';
		i = 0;
		j = 0;
		for (j=0; j< num_of_cities; j++)
		{
		add_distances.distance.push_back(INT_MAX);
		add_distances.complete.push_back(0);
		add_distances.cities.push_back(nodes[j].name);
		}
		distances = add_distances;
		distances.path.push_back(temp_from);
		distances.currentdistance.push_back(0);
		distances.fromwhere.push_back(temp_from);
		i=0;
		j=0;
		k=0;
		m=0;
		l=0;
		min = INT_MAX;
		while ( (i < num_of_cities) && (temp_from != temp_to))
		{
			cout << temp_from;
			if (temp_from == nodes[i].name)
			{
				distances.complete[i] = 1;
				for (j=0; j < nodes[i].edges.size(); j++)
				{
					for(k=0; k < num_of_cities; k++)
					{
						if (nodes[i].edges[j] == distances.cities[k])
						{
						if (distances.distance[k] > nodes[i].dist[j]+distances.currentdistance[distances.currentdistance.size()-1])
							distances.distance[k] = nodes[i].dist[j]+distances.currentdistance[distances.currentdistance.size()-1];
							
						}
					}
				}
				for (l = 0; l < (distances.distance.size()); l++)
				{
					if ((distances.distance[l] + distances.currentdistance[distances.currentdistance.size()-1] < min) && (distances.distance[l]  != 0))
					{
						if (distances.distance[l] != INT_MAX)
						{
							if (distances.complete[l]  == 0)
							{
							min = distances.distance[l];
							wheremin = l;
							}
						}
					}
				}
				distances.complete[wheremin] = 1;
				distances.currentdistance.push_back(min);
				distances.path.push_back(nodes[wheremin].name);
	
				temp_from = nodes[wheremin].name;
				i= 0;
				j=0;
				k=0;
				min = INT_MAX;
			}
			else
				i++;
		}
		cout << "done";
		
	}
	cin >> c;
	return 0;

}

This is what i have so far, I'm finding it hard to print out the path it takes and the total distance. Please give me help!

P.S i have attached the files for it, also i know there's a lot of jibberish in it but I've being trying so much with fail. :(

Edited 5 Years Ago by imhiya: n/a

Attachments
Hull	Liverpool
Leeds	Bristol
Glasgow	Northampton
York	Hull	60
Leeds	Doncaster	47
Liverpool	Nottingham	161
Manchester	Sheffield	61
Reading	Oxford	43
Oxford	Birmingham	103
Birmingham	Leicester	63
Liverpool	Blackpool	79
Carlisle	Newcastle	92
Nottingham	Birmingham	77
Leeds	York	39
Glasgow	Edinburgh	74
Moffat	Carlisle	65
Doncaster	Hull	76
Northampton	Birmingham	90
Leicester	Lincoln	82
Sheffield	Birmingham	122
Lincoln	Doncaster	63
Sheffield	Doncaster	29
Bristol	Reading	130
Hull	Nottingham	145
Blackpool	Leeds	116
Birmingham	Bristol	139
Manchester	Leeds	64
Carlisle	Blackpool	140
Leicester	Northampton	61
Newcastle	York	135
Glasgow	Moffat	78
Leicester	Sheffield	100
Birmingham	Manchester	129
Oxford	Bristol	116
Leeds	Hull	89
Edinburgh	Carlisle	154
Nottingham	Sheffield	61
Liverpool	Manchester	56
Sheffield	Lincoln	74
York	Doncaster	55
Newcastle	Edinburgh	177
Leeds	Sheffield	53
Northampton	Oxford	68

Way too much cruft to sort through quickly here. Remember the motto "KISS" - so, simplify your code down to the bare essentials, and take all those big loops and refactor them into function calls. That way, each function point (call) can be much more easily analyzed in detail, and side effects are minimized.

Ok, I've changed it a lot myself. I'm implementing this algorithm; http://compprog.files.wordpress.com/2008/01/dijkstra.c . but i want it for a given source to given target.

Sorry, but I don't get what you mean with "i want it for a given source to given target." - please explain. The source shown, while not what I'd let my engineers get away with releasing into production, will work (from the little I was able to study it). What is your actual intention here?

This article has been dead for over six months. Start a new discussion instead.