0

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



}
2
Contributors
6
Replies
22
Views
3 Years
Discussion Span
Last Post by dreday92
0

I am not able to find the shortest route, I dont even know where to start, I thought the BFS did that

0

example1

Attachments
8
Atlanta
Denver
New York
Orlando
Pittsburgh
San Diego
Seattle
Tallahassee
  0 100   -1   50   -1   -1    -1   100
100   0   -1   -1   50   10    -1    -1
 -1  -1    0 1000  200   -1  1000    -1
 50  -1 1000    0   -1   -1    -1    -1
 -1  50  200   -1    0   -1   100    -1
 -1  10   -1   -1   -1    0    50  2000
 -1  -1 1000   -1  100   50     0    -1
100  -1   -1   -1   -1 2000    -1     0
0

It say we have to use BFS, but if two of the shortest paths are the same then it doesnt matter which one we print out

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.