Digraph question- Flight path

Microsoft Visual studio 2008 professiona...
June 22, 2010 at 07:54:18
Specs: Windows 7
I am trying to use a digraph to read in airline flight information from a file and then ask the user for the source and destination then print out the path to get there.
the text file contains source, destination, miles, cost.

I am having problems making it use the cost as the weight when determining the shortest path and adding up the miles. It doesn't associate the right cost with the different paths.

I would be happy just to make it add up the correct total cost and miles. Right now my code is doing an unweighted calculation and trying to add up the total cost. Here is the part of my code where I am adding the data then doing the calculation.

void Graph::addFlight( const string & sourceName, const string & destName, int miles, int cost )
{
    Location * v = getLocation( sourceName );
    Location * w = getLocation( destName );
    v->adj.push_back( w );
	v->dist1 = cost;
	v->dist2 = 0;
	
}
void Graph:: shortestPath( const string & startName )
{
    clearAll( );

    vmap::iterator itr = LocationMap.find( startName );

    if( itr == LocationMap.end( ) )
    {
        cout << startName << " is not a vaild Location" << endl;
        return;
    }

    Location *start = (*itr).second;
	list<Location *> q;
    q.push_back( start ); start->dist = 0;
	start->dist2 = 0;
	start->dist1;

    while( !q.empty( ) )
    {
        Location *v = q.front( );	q.pop_front( );

        for( int i = 0; i < v->adj.size( ); i++ )
        {
            Location *w = v->adj[ i ];
            if( w->dist == INFINITY )
            {
                w->dist = v->dist + 1;
				w->dist2 = v->dist1 + w->dist2;
                w->path = v;
                q.push_back( w );
            }
        }
    }
}

sample data file (source, destination, miles, cost):
SFA SLC 700 59
SFO LV 420 39
LAX LV 231 23
LV SLC 362 29
LAX SFO 344 39
LAX SLC 581 57
SFA SFO 679 67
SFO SLC 605 19
PHX DEN 586 65
LV PHX 256 21
DEN SFA 1026 72
DEN LAX 844 69
SLC DEN 379 49
SLC SJC 585 29
SJC SFO 51 19

Thanks for your help.


See More: Digraph question- Flight path

Report •

#1
June 22, 2010 at 13:57:51
I'm just not good enough to see a small snippet of code, and instantly know all there is to know about its much larger project.

That said,

    q.push_back( start ); start->dist = 0;
	start->dist2 = 0;
	start->dist1;

I notice you're not setting start->dist1 to anything.

Report •
Related Solutions


Ask Question