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