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



}

...what's the issue?

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

Can you post a sample of your file?

example1

This post has no text-based content.

If the paths have different positive weights you'll want to use something like Dijkstra's algorithm for the shortest path instead of BFS. BFS assumes a universal path weight of 1 unless you make modifications.

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

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.