Made Easy Test Series: Computer Network-Dijkstra Algo

1 vote
146 views

Consider Dijkstra’s algorithm in linked state routing protocol at node $u.$ Professor Ram first sets the route for each directly connected node $v.$ to be the link connecting $u$ to $v.$ Ram then implements the rest of the algorithm correctly, aiming to produce minimum cost routes, but doesnot change the routes to the directly connected nodes. In this network, u has atleast two directly connected nodes and there is more than one path between any two nodes. Which of the following statement is false with u’s routing table?

$A)$ There are topologies and link costs where the majority of the routers to other nodes will be incorrect?

$B)$ There are topologies and link costs where no routing table entry (other than u to itself) will be correct.

$C)$ There are topologies and link costs where all routing table entry will be correct.

$D)$ Both $A)$ and $B)$

How Dijkstra working here?

0
c?
0
how??

not getting. Can u explain a bit first.
0

Consider this diagram and verify the above condition and option c, see that all conditions are satisfied.

First adjacent node's weights of u are all made constant, now apply dijkstra at each node, it will always give the best result even after fixing the weights of 2 adjacent paths of u.

0

@Hirak

they r asking for u's routing table. Where u constructed it??

0
Sorry..! i thought the question was asking which one is the correct in options.. but now i saw that false was asked for.. but tell me one thing, if i even consider routing table for my above diagram for u, i will be getting the best routing table like

u--> a =4

u--> c=5

u->a->b = 6.

Is C the ans (as wrong)?

So where did i go wrong?
0
no, ans given B)

Related questions

1
267 views
Consider a very large network $10000$ routers. Two host $A$ and $B$ connected with this network. Host $A$ sends a data to host $B$. and after some unit of time host $A$ receives $ICMP$ time exceed message for the samedata packet. The number of router ... some distance some ICMP message generated? Say if $ICMP$ message generated in $9999th$ router, then where it give error of time exceed message?
Which of the following procedure results same output as Dijkstra’s Algo. on unweighted graph on $'n'$ verices? $A)$ BFS $B)$ DFS $C)$Kruskal $D)$ Prims As far I know Dijkstra and Prims both have $T.C.=O(E+VlogV)$ But ans given BFS. How this ans possible??