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:
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.
0
, your program output should look like the following.
shortest path to node 1 is 0->1 with cost 2.0 shortest path to node 2 is 0->3->4->2 with cost 3.0 shortest path to node 3 is 0->3 with cost 1.0 shortest path to node 4 is 0->3->4 with cost 2.0 shortest path to node 5 is 0->3->4->5 with cost 4.0Note 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: