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 )
{
    /* 调用load_services读取 */
    load_services( filename );
}


void RailSystem::load_services( string const &filename )
{
    /* 读取数据建立两个map */
    ifstream    inf( filename.c_str() );
    string      from, to;
    int     fee, distance;

    while ( inf.good() )
    {
        /* 文件正常则读入出发地，目的地，费用，距离 */
        inf >> from >> to >> fee >> distance;

        if ( inf.good() )
        {
            Service* s = new Service( to, fee, distance );
            /* 若列表中没有出发城市就加入 */
            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 ); /* 在出发城市直连城市链表的尾部加入数据 */
        }
    }
    inf.close();
}


RailSystem::~RailSystem( void )
{
    /* 析构函数，释放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 )
{
    /* 输出最短路径，调用calc_route计算最短路径 */
    reset();
    pair<int, int> totals = calc_route( from, to );

    if ( totals.first == INT_MAX ) /* 费用依然为最大说明无法到达 */
    {
        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函数 */
    return(cities.count( name ) == 1);
}


pair<int, int> RailSystem::calc_route( string from, string to )
{
    /* 优先权队列获得下一个城市的最小花费 */
    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 ); /* 队列尾部加入出发城市 */
    /* 优先权队列不为空时 */
    while ( !candidates.empty() )
    {
        /* 要访问的城市 */
        City* visiting_city;
        /* 将头部城市设为要访问的城市 */
        visiting_city = candidates.top();
        candidates.pop();                       /* 顶部城市出队 */
        /* 若未访问过此城市 */
        if ( !visiting_city->visited )
        {
            visiting_city->visited = true;  /* 设为已访问 */
            /* 遍历这个城市的直连城市 */
            list<Service*>::iterator it;
            for ( it = outgoing_services[visiting_city->name].begin(); it != outgoing_services[visiting_city->name].end(); ++it )
            {
                /* 将目的地设为下一个城市 */
                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);
}