Skip to Content

COMP225 : Algorithms and Data Structures

Assignment 3 : Cheapest Airfares 

                           Mandatory Checkpoint 1 :  May 24th, 6pm.
                                Mandatory Checkpoint 2 May 28th, 6pm.
Worth 10%                       Final deadline : Sunday May 31st, 11.59pm.

Objectives

To learn more about graph algorithms and STL containers. To recognize the importance of developing, coding and testing systematically.

Overview

Cheaper airfares can sometimes be found by travelling via different routes. This program reads in a file listing the cost of flights between cities, prompts and reads in a start city and reports the cheapest route from the start city to all other cities.

Details

  1. Each line of the file consists of two cities and a cost, delimited by tabs. All data is in correct format. There is a maximum of 100 different cities in a file.
  2. We will use Dijkstra's Shortest Path algorithm to determine the cheapest cost between the cities.
  3. The cheapest cost to each city will be displayed in alphabetical order of cities.
  4. When there is more than one cheapest route the one with the least number of flights will be shown.
  5. Sample Input/Output
  6. Sample Input/Output
  7. Sample Input/Output
  8. Unix executable
  9. Windows executable
  10. sample data file
  11. sample data file

Program Development

  1. Understand Dijskra's shortest path algorithm.
  2. Complete and test the practical exercise to associate a string with an int (and vice versa).
  3. Write dump routines to dump out the contents of your data structures during program development (to help with debugging and to save your sanity).

Submit

Submit whatever files you wish as long as they compile and run on unix using g++ *.c*

Assessment

There will be 8 marks for autotesting using graded data (from very simple (say only 3 cities) to those with more routes and choices). To obtain marks for the autotesting your program needs to match the output from sample program (except for whitespace). On unix use diff-wi to compare outputs. It is strongly recommended that you submit early and obtain useful feedback from checkpoints and previews.

There will be 2 marks for style marked in practical week 13 (by ros). Your program should be modular, readable, well-documented and contain simple elegant code.

I hope you enjoy writing this program and can see how it could be extended to be even more useful.

All comments to ros