Prerequisites, Goals, and Outcomes

Prerequisites: Students should have mastered the following prerequisite skills.

• Graphs - Knowledge of graph representation
• Graph Algorithms - Knowledge of Dijkstra's shortest path algorithm

Goals: This assignment is designed to reinforce the student's understanding of the implementation of a fundamental graph algorithm

Outcomes: Students successfully completing this assignment would master the following outcomes.

• Understand graph representation
• Understand how to implement Dijkstra's shortest path algorithm
  Background
  Traveling through Europe by rail is a cheap and effective way to experience the sights, sounds, and culture of a wide array of countries and cities. Generally, travelers purchase rail passes that allow unlimited travel on the rail system. Individual tickets, however, can be purchased.
  Description
  The program for this assessment calculates the cheapest route between two cities in a mock European rail system. The graph that represents the rail system is pictured below.

image.png

//RailSystem.cpp要寫的只有這個
#include "RailSystem.h"

void RailSystem::reset( void )
{
    /* 遍歷cities，初始化城市信息 */
    map<string, City*>::iterator it;
    for ( it = cities.begin(); it != cities.end(); ++it )
    {
        it->second->visited     = false;        /* 初始未被訪問 */
        it->second->total_fee       = INT_MAX;      /* 初始值為最大 */
        it->second->total_distance  = INT_MAX;      /* 初始值為最大 */
        it->second->from_city       = "";
    }
}


RailSystem::RailSystem( string const &filename )
{
    /* 調(diào)用load_services讀取 */
    load_services( filename );
}


void RailSystem::load_services( string const &filename )
{
    /* 讀取數(shù)據(jù)建立兩個map */
    ifstream    inf( filename.c_str() );
    string      from, to;
    int     fee, distance;

    while ( inf.good() )
    {
        /* 文件正常則讀入出發(fā)地，目的地，費用，距離 */
        inf >> from >> to >> fee >> distance;

        if ( inf.good() )
        {
            Service* s = new Service( to, fee, distance );
            /* 若列表中沒有出發(fā)城市就加入 */
            if ( cities.count( from ) == 0 )
            {
                cities[from]        = new City( from );
                outgoing_services[from] = list<Service*>();
            }
            /* 若列表中沒有目的城市就加入 */
            if ( cities.count( to ) == 0 )
            {
                cities[to]      = new City( to );
                outgoing_services[to]   = list<Service*>();
            }
            outgoing_services[from].push_back( s ); /* 在出發(fā)城市直連城市鏈表的尾部加入數(shù)據(jù) */
        }
    }
    inf.close();
}


RailSystem::~RailSystem( void )
{
    /* 析構(gòu)函數(shù)，釋放City map和Service map中的指針 */
    map<string, City*>::iterator city_it = cities.begin();
    for (; city_it != cities.end(); city_it++ )
    {
        delete city_it->second;
    }
    map<string, list<Service*> >::iterator services_it =
        outgoing_services.begin();
    for (; services_it != outgoing_services.end(); services_it++ )
    {
        list<Service*>::iterator service_it = services_it->second.begin();
        for (; service_it != services_it->second.end(); service_it++ )
        {
            delete *service_it;
        }
    }
}


void RailSystem::output_cheapest_route( const string & from,
                    const string & to, ostream & out )
{
    /* 輸出最短路徑，調(diào)用calc_route計算最短路徑 */
    reset();
    pair<int, int> totals = calc_route( from, to );

    if ( totals.first == INT_MAX ) /* 費用依然為最大說明無法到達(dá) */
    {
        out << "There is no route from " << from << " to " << to << "\n";
    } else {
        out << "The cheapest route from " << from << " to " << to << "\n";
        out << "costs " << totals.first << " euros and spans " << totals.second
            << " kilometers\n";
        cout << recover_route( to ) << "\n\n";
    }
}


bool RailSystem::is_valid_city( const string & name )
{
    /* 判斷是否存在城市的bool函數(shù) */
    return(cities.count( name ) == 1);
}


pair<int, int> RailSystem::calc_route( string from, string to )
{
    /* 優(yōu)先權(quán)隊列獲得下一個城市的最小花費 */
    priority_queue<City*, vector<City*>, Cheapest> candidates;

    /* Dijkstra最短路徑算法： */

    /* 將起點初始化加入隊列 */
    City* start_city = cities[from];
    start_city->total_fee       = 0;
    start_city->total_distance  = 0;
    candidates.push( start_city ); /* 隊列尾部加入出發(fā)城市 */
    /* 優(yōu)先權(quán)隊列不為空時 */
    while ( !candidates.empty() )
    {
        /* 要訪問的城市 */
        City* visiting_city;
        /* 將頭部城市設(shè)為要訪問的城市 */
        visiting_city = candidates.top();
        candidates.pop();                       /* 頂部城市出隊 */
        /* 若未訪問過此城市 */
        if ( !visiting_city->visited )
        {
            visiting_city->visited = true;  /* 設(shè)為已訪問 */
            /* 遍歷這個城市的直連城市 */
            list<Service*>::iterator it;
            for ( it = outgoing_services[visiting_city->name].begin(); it != outgoing_services[visiting_city->name].end(); ++it )
            {
                /* 將目的地設(shè)為下一個城市 */
                City    * next_city = cities[(*it)->destination];
                int next_fee    = (*it)->fee + visiting_city->total_fee;
                /* 新的費用值小于舊的時替換 */
                if ( (next_fee < next_city->total_fee) && next_city->name != from )
                {
                    next_city->total_fee        = next_fee;
                    next_city->total_distance   =
                        (*it)->distance + visiting_city->total_distance;
                    next_city->from_city = visiting_city->name;
                    candidates.push( next_city );
                }
            }
        }
    }
    /* 返回總費用和總路程，否則返回最大值 */
    if ( cities[to]->visited )
    {
        return(pair<int, int>( cities[to]->total_fee, cities[to]->total_distance ) );
    } else {
        return(pair<int, int>( INT_MAX, INT_MAX ) );
    }
}


string RailSystem::recover_route( const string & city )
{
    /* 利用棧保存最小費用路線中的城市名，以此返回正序排列的城市字符串 */
    string  route;
    string  current = city;
    while ( current != "" )
    {
        route = current + route;
        string prev = cities[current]->from_city;
        if ( prev != "" )
        {
            route = " to " + route;
        }
        current = prev;
    }
    return(route);
}