Starting from:
$30
CS3700-Homework 9 Dijkstra’s Algorithm Solved
Part I : 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 <link cost between these two routers
… … … 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 : Test your programs on the Virtual Server cs3700a.msudenver.edu
(more on next page!)
Warning: to complete this part, especially when you work at home, you must first (1) connect to GlobalProtect using your NetID account
• 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 <link cost between these two routers
… … … 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 : Test your programs on the Virtual Server cs3700a.msudenver.edu
(more on next page!)
Warning: to complete this part, especially when you work at home, you must first (1) connect to GlobalProtect using your NetID account
1 file (189.8KB)
