Assignment #2 - Implementing Dijkstra's Algorithm for Link State Routing

Due by 11:59pm, Sunday, October 20.

Assignment requirements:
In this assignment you are asked to implement Dijkstra's Algorithm for link state routing. For a given network topology and cost of each link, your program should find the shortest paths to all destination nodes from a given source node. In order to design your program with the lowest possible complexity, you should pay special attention to the following:

This is an individual assignment, so each person should turn in his/her own.

Input/output format and testing:
Your program should take a text file as input, which describes the network topology. The first line of the text file is a single number, which stands for the number of nodes in the network. With a network of n nodes, we assume the nodes have the following IDs: 0, 1, ..., n-1. All subsequent lines in the input file are in the format of "n1 n2 cost", which stands for a link between node n1 and node n2 with cost cost. Note that cost can be a floating point number. These three numbers are separated by single spaces in each line of the input file. All the links are bidirectional. So a link of "n1 n2 cost" infers a link of "n2 n1 cost". All links are sorted in ascending order with n1 as the primary order and n2 as the secondary order.

As output, your program should print out the shortest path to all network nodes with the complete path and the cost.

Let's look at an example with the network topology shown in the following figure.

The input file will look like network.dat. If the source node is node 0, your program output should look like the following. Note that we will use DIFFERENT network topology in our testing.

Turn-in:
You are asked to turn in a single source file and a README file. The source file should be named LinkState.c if you use C, LinkState.cpp if you use C++, and LinkState.java if you use Java. In the case of Java, the main class should also be called LinkState such that your program can be launched as "java LinkState ..." after compile. No matter what programming language you choose to use, your program should take two parameters on startup. The first parameter is the path of a text file describing the network topology. The second parameter is the ID of the source node. For example, if your program is written in Java, you should be able to run your program using "java LinkState network.dat 0" to find shortest paths from node 0 in the network topology specified by network.dat.

The README file should contain a description of your design, and a detailed analysis of the complexity of your program. If your program requires any special compilation flag to build, you need to specify the full build command in the README file. Alternatively, you can provide a makefile, which is strongly preferred.

The turn-in procedure is the same as the first assignment.

Grading: