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



}

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

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

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 article has been dead for over six months. Start a new discussion instead.