CS 3700 Homework 9: Dijkstra’s Algorithm solution


Original Work ?


5/5 - (3 votes)

Part I (90%):

Write a Java program to build up the forwarding table at source router V0 using the Dijkstra’s algorithm.

• The routers in the network are labeled as V0, V1, V2, …, etc (for display, such labels are required to use, please do NOT use 0, 1,
2, 3, … etc. However, it is perfectly okay for you to use indices 0, 1, …, and n – 1 internally in your program.)

• Your routing program needs to
1. Display a prompt message to ask the user to input the total number of routers, n, in the network. Validate n to make sure that
it is greater than or equal to 2.

2. Use a topo.txt file that contains costs of all links. Each line in this file provides the cost between a pair of routers as below,
where tab (‘\t’) is used to separate the numbers in each line.
<# of one router> <# of the other router> … … …
where the first and the second numbers in each row need to be validated to be between 0 and n – 1, the third number needs to
be validated to be positive. For example, for the link (V0, V3) whose cost is 10, only ONE of the following two lines needs
to be included in the topo.txt file.

0 3 10 // only ONE of this or the next line needs to be included in the topo.txt file
3 0 10 // only ONE of this or the above line needs to be included in the topo.txt file
This topo.txt file can locate in the same directory where this program runs such that a path is not needed.

Display a message
saying that in which row the first invalid number is detected, close the txt file, and KEEP asking for the name of the cost input
file until all numbers are checked to be valid. Record the cost information in the Cost matrix.

3. Implement the Dijsktra’s algorithm to build up the shortest-path tree rooted at source router V0. As the intermediate results, at
the end of Initialization and each iteration of the Loop, display
The set N’
The set Y’
The distance vector D, i.e., D(i) for each i between 1 and n – 1
The predecessor vector P, i.e., p(i) for each i between 1 and n – 1

4. Use the shortest-path tree resulted from the Dijsktra’s algorithm to build up the forwarding table for router V0. Display the
forwarding table in the following format:
Destination Link
V1 (V0, …)
V2 (V0, …)

Vn-1 (V0, …)

Part II (10%):

Test your programs on the Virtual Server cs3700a.msudenver.edu
(more on next page!)

MSU Denver, M&CS CS 3700-001: Computer Networks, Spring 2020 Dr. Weiying Zhu
Warning: to complete this part, especially when you work at home, you must first (1) connect to GlobalProtect using your NetID
account (please read “how to connect to GlobalProtect …” at https://msudenver.edu/vpn/); then (2) connect to the virtual servers
cs3700a using sftp and ssh command on MAC/Linux or PUTTY and PSFTP on Windows.

ITS only supports GlobalProtect on MAC and Windows machines. If your home computer has a different OS, it is your responsibility
to figure out how to connect to cs3700a for programming assignments and submit your work by the cutoff deadline. Such issues cannot
be used as an excuse to request any extension.

1. MAKE a directory “HW9” under your home directory on cs3700a.msdenver.edu
2. UPLOAD and COMPILE your program under “HW9” on cs3700a.msdenver.edu
3. TEST your program running on cs3700a.msudenver.edu
4. SAVE a file named testResultsClient.txt under “HW9” on cs3700a.msudenver.edu, which captures the outputs of your program
when you test it.

You can use the following command to redirect the standard output (stdout) and the standard error (stderr) to a
file on UNIX, Linux, or Mac, and view the contents of the file
java prog_name_args | tee testResultsClient.txt //copy stdout to the .txt file
//if you want, you may also use “script” command instead of the “tee” command
//to write both stdin and stdout into testResultsClient.txt while testing your
//client program on cs3700a. For how to use “script”, see
// https://www.geeksforgeeks.org/script-command-in-linux-with-examples/
//or Google “script command in Linux” if the above link is broken.
cat file-name //display the file’s contents.