Calculate the paths of a simulated network using the three following algorithms from the supplied text, comparing run times of each

Table $4\mathrm{.}4$ Distance$-$Vector Routing Algorithm for A Node

Distance$\_$Vector$\_$Routing $()$

$\{$

$//$ Initialize $($create initial vectors for the node$)$

D$[$myself$]=0$

for $($ y $=1$ to N$)$

$\{$

if $(\}$y$\backslash$mathrm$\{$ is a neighbor$)$

D$[$y$]=$c$[$myself$[$y$]$

else

D$[$y$]=\backslash$infty

$\}$

send vector $\{$D$[1],$ D$[2],...,$ D$[$N$]\}$ to all neighbors

$//$ Update $($improve the vector with the vector received from a neighbor$)$

repeat $($forever$)$

$\{$

wait $($for a vector D

for $($ y $=1$ to N$)$

$\{$

D$[$y$]=$min $[$D$[$y$],($c$[$myself$][$w$]+$ D

$\}$

if $($any change in the vector$)$

send vector $\{$D$[1],$ D$[2],...,$D$[$N$]\}$ to all neighbors

$\}$

$\}//$ End of Distance Vector

Dijkstra's Algorithm $()$

$\{$

$//$ Initialization

Tree $=\{$root $\}//$ Tree is made only of the root

for $($ y$=1$ to N$)//$ N is the number of nodes

$\{$

if $(\}$y$\backslash$mathrm$\{$ is the root$)$

D$[$y$]=0//$ D $[$y$]$ is shortest distance from root to node y

else if $(\}$y$\backslash$mathrm$\{$ is a neighbor$)$

D$[$y$]=$c$[$root$][$y$]//$ c$[$x$][$y$]$ is cost between nodes x and y in LSDB

else

D$[$y$]=\backslash$infty

$\}$

$//$ Calculation

repeat

$\{$

find a node w$,$ with D$[$w$]$ minimum among all nodes not in the Tree

$//$ Update distances for all neighbor of w

for $($every node x$,$ which is neighbor of w and not in the Tree$)$

$\{$

D $[$ x $]=\backslash$operatorname $\{$ m i n $\}\{$ D $[$ x $],($ D $[$ w $]+$ c $[$ w $][$ x $])\}$

$\}$

$\}$ until $($all nodes included in the Tree$)$

$\}//$ End of Dijkstra

Table $4\mathrm{.}6$ Path$-$vector algorithm for a node

Path$\_$Vector$\_$Routing $()$

$\{$

$//$ Initialization

for $($ y $=$ l to N$)$

$\{$

if $($y is myself$)$

Path $[$y$]=$ myself

else if $($y is a neighbor$)$

Path$[$y$]=$ myself $+$ neighbor node

else

Path $[$y$]=$ empty

$\}$

Send vector $\{$Path$[1],$ Path$[2],...,$ Path$[$y$]\}$ to all neighbors

$//$ Update

repeat $($forever$)$

$\{$

wait $($for a vector Path from a neighbor w$)$

for $($ y $=$ l to N$)$

$\{$

if $($Path $ includes myself$)$

discard the path $//$ Avoid any loop

else

$\}$

If $($there is a change in the vector$)$

Send vector $\{$Path$[1],$ Path$[2],...,$ Path$[$y$]\}$ to all neighbors

$\}$

$\}//$ End of Path Vector

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 $\backslash ($ n $\backslash )$ nodes, we assume the nodes have the following IDs: $\backslash (0,1,\backslash$ldots$,$ n$-1\backslash ).$ All subsequent lines in the input file are in the format of $"\backslash ($ n $1\backslash )$ n$2$ cost$",$ which stands for a link between node $\backslash ($ n $1\backslash )$ and node $\backslash ($ n $2\backslash )$ 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 $"$n$1$ n$2$ cost $"$ infers a link of $"$n$2$ n$1$ cost $".$ All links are sorted in ascending order with n $1$ as the primary order and n $2$ 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.

$```$

Distance Vector Routing:

shortest path to node $1$ is $0->1$ with cost $2\mathrm{.}0$

shortest path to node $2$ is $0->3->4->2$ with cost $3\mathrm{.}0$

shortest path to node $3$ is $0->3$ with cost $1\mathrm{.}0$

shortest path to node $4$ is $0->3->4$ with cost $2\mathrm{.}0$

shortest path to node $5$ is $0->3->4->5$ with cost $4\mathrm{.}0$

Time Elapsed: $5$ seconds

Djikstra's Algorithm:

$....($Repeat for the other $2$ algorithms$)$

$```$

Note that we will use DIFFERENT network topology in our testing. 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 if you use C$,$ if you use C$++,$ and a if you use Java, and Distance.py if you use Python. In the case of Java, the main method class should also be in Distance such that your program can be launched as $\text{'}"$ 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 Distance network. dat $0"$ to find shortest paths from node 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.