Algorithms Assignment -

TASK -

1. Design and implement an efficient algorithm for determining the best route between two given stations in a given rail network.

2. The rail network should be passed to your program as an input. We will use a simplified version of the Sydney CityRail network given to you in RailNetwork.xml

3. Your program should NOT take into account the time of the day, but rather use an average time to travel from a station to a station on a particular line, and a flat time of 15min needed to change from one line to another. This information will be given as a part of the input rail network data.

4. Your task is to optimise the route based on the time traveled.

Your program should contain a header with information about what it does and what the input and output are. You must use a version of Dijkstra's algorithm that uses adjacency lists and indirect heaps.

Your program should also contain inline comments and be easy to follow.

The programs should be written in Java or C++.

INPUT -

Your program must be able to be used from the command line and must accept all input as command line arguments.

1. Your program must take as an input the name (including path if necessary) of an XML file containing an undirected graph of the rail network:

• The graph is provided as a list of neighbours for each vertex in the graph.
• Each vertex corresponds to a station in the network, and each vertex name consists of 2 strings: The name of the station, and the name of the rail line. A single station might thus be represented by multiple vertices if it is on multiple lines.
• Each entry in the list of neighbours of vertex v contains the name of the neighbouring vertex, say u, followed by the weight of the edge vu. If the vertices v and u are on the same line, the weight of the edge vu is the time in minutes needed to travel from vertex v to vertex u (or vice-versa - it is assumed that the time is the same for both directions). If the vertices v and u are not on the same line, the weight of the edge vu is 15 (we are assuming that it takes 15 minutes to change lines at a station).

A sample input file RailNetwork.xml will be provided in Blackboard. You don't need to create other input files - you can use this one for the purpose of developing and testing your assignment.

It is advised that you investigate the many pre-existing libraries (for Java or C++) available for working with XML and incorporate those into your program. Then, reading the data from the xml file and navigating the data should amount to (reasonably) simple calls to the classes and methods of the library in question.

2. Your program must accept as input the names of two stations, say X and Y.

The order of command line arguments must be: xml file, station 1, station 2, optimisation criterion (if appropriate) see SUBMISSION section, below for more information.

OUTPUT

1. Individual assignment:

You program must output the quickest route in the following format: From X, take line a to station Z; then change to line b, and continue to W; then change to line c, and continue to Y. The total trip will take approximately n minutes.

Attachment:- Assignment Files.rar