#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. :(

Recommended Answers

All 3 Replies

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?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.