I am having an issue implementing the Breadth First Search, Im trying to find the shortest distance between the source city and the destination city. Here is what I have so far, Im stuck and dont know what to do about this issue.
#include <iostream>
#include <string>
#include <fstream>
#include <iterator>
#include <algorithm>
#include "Queue.h"
using namespace std;
using namespace cop4530;
struct Airline
{
string city;
int col;
int row;
};
int main(int arg, char* filename[])
{
fstream Filename;
string fileinput;
string * cities;
Airline paths;
int ** travelgrid;
int Citymax;
int index = 0;
Filename.open(fileinput.c_str(), ios::in);
Queue<Airline> flightplan,temporary;
Queue<string>flightroute;
Airline * cityinfo;
bool found = false;
bool * doesntexist;
Filename.open("Cities.txt");
Filename >> Citymax;
Filename.ignore();
cities = new string [Citymax];
travelgrid = new int*[Citymax];
for (int i = 0; i < Citymax; i++)
{
travelgrid[i] = new int [Citymax];
}
cout << Citymax << " Cities: " << endl;
for (int i = 0; i < Citymax; i++)
{
getline(Filename,cities[i]);
cout << cities[i] << endl;
}
cout << endl;
cout << "direct flights between cities " << endl;
cout << "-------------------------" << endl;
for (int i = 0; i < Citymax; i++)
{
for (int j = 0; j < Citymax; j++)
{
Filename >> travelgrid[i][j];
}
}
for (int i = 0; i < Citymax; i++)
{
cout << cities[i] << ": " << endl;
for (int j = 0; j< Citymax; j++)
{
if (travelgrid[i][j] > 0)
{
cout << " " << cities[j] << ", $" << travelgrid[i][j] << endl;
}
}
}
doesntexist = new bool [Citymax];
for (int j = 0; j < Citymax; j++)
{
doesntexist[j] = false;
}
string decision;
do
{
cout << "Source City: " ;
string scity, dcity;
getline(cin, scity);
cout << "Destination City: ";
getline(cin, dcity);
//bool *visited = new bool[Citymax];
for (int i = 0 ; i < Citymax; i++)
{
if(scity == cities[i])
{
cityinfo = new Airline;
cityinfo->city = scity;
cityinfo->col = i;
index= i;
flightplan.push(*cityinfo);
delete cityinfo;
doesntexist[i] = true;
}
}
cout << flightplan.front().city << endl;
cout << flightplan.front().col << endl;
while (!found)
{
for(int j = 0; j < Citymax; j++)
{
if(travelgrid[index][j] > 0)
{
cout << cities[j];
cout << "First Connection City # " << j;
cout << "First Connection City price" << travelgrid[index][j] << endl;
cityinfo = new Airline;
cityinfo->city = scity;
cityinfo->col = j;
if (!doesntexist)
{
flightplan.push(*cityinfo);
doesntexist[j]= true;
}
delete cityinfo;
if (cities[j]== dcity)
{
found = true;
}
cout << " " << j << " Ya bish";
cout << " " << travelgrid[paths.col][j];
cout << endl;
}
}
}
flightroute.push(flightplan.front().city);
flightplan.pop();
index = flightplan.front().col;
/*while(!Q.empty()) {
u is the starting node
u = Q.top().first;
Q.pop();
if(F[u]) continue; //If already done forget it
sz = G[u].size();*/
while (!flightroute.empty())
{
for (int i = 0; i < Citymax; i++)
{
//int sz;
//string u;
//u = flightroute.front();
flightroute.pop();
//if (doesntexist[i]) continue;
//sz = travelgrid[i][j].size();
cout << flightroute.front() << " -> ";
}
}
cout << dcity << " " << endl;
cout << "Search another route? ";
getline(cin,decision);
}while (decision == "y" || decision == "Y" || decision == "Yes" || decision == "YES" || decision == "yes");
Filename.close();
}
