SRM INSTITUTE OF SCIENCE AND TECHNOLOGY
NCR Campus Delhi, Meerut Road, ModiNagar, Uttar Pradesh 201204
21CSC302J-COMPUTER NETWORKS
ASSIGNMENT-1
NAME: REG.NO: SEC:
Question.1:Using bellman ford algorithm find shorest path from a vertex to all other vertices using
below given weighted graph.
Solution:
If(d(u)+c(u,v)<d(v))
Then d(v)=d(u)+c(c,v)
1st Iteration
Visited
Vertex
A B C D E F
2nd Iteration
Visited
Vertex
A B C D E F
3rd Iteration
Visited
Vertex
A B C D E F
4th Iteration
Visited
Vertex
A B C D E F
A
Question.2: Using following directed graph find the shortest path.
Solution:
Using vertex 5 as the source (setting its distance to 0), we initialize all the other distances to ∞.
Iteration 1:
Iteration 2:
Iteration 3:
Iteration 4:
The final shortest paths from vertex 5 with corresponding distances is
Negative cycle checks: We now check the relaxation condition one additional time for each edge. If
any of the checks pass then there exists a negative weight cycle in the graph.
v3.d > u1.d + w(1,3) ⇒ ……. ≯……. + ……. = …….
v4.d > u1.d + w(1,4) ⇒ ……. ≯ ……. +……. =………
v1.d > u2.d + w(2,1) ⇒……. ≯……. +……. = ……….
v4.d > u3.d + w(3,4) ⇒ ……. ≯……. +……. =…….....
v2.d > u4.d + w(4,2) ⇒……. ≯……. +……. =…………
v3.d > u4.d + w(4,3) ⇒……. ≯……. +……. =…………
v2.d > u5.d + w(5,2) ⇒……. ≯……. + ……. = ………
v4.d > u5.d + w(5,4) ⇒……. ≯ ……. + ……. =……….
Note: That for the edges on the shortest paths the relaxation criteria gives equalities. Additionally,
the path to any reachable vertex can be found by starting at the vertex and following the π's back to
the source.
Starting at vertex 1, u1.π = ……, u2.π = ………, u4.π= ……….
⇒ Then shortest path to vertex 1 is {…… ……. ……. ………}.
Question.3:Using bellman ford algorithm find shorest path from a vertex to all other vertices using
below given weighted graph.
Solution:
Iteration 1:
NODE SHORTEST COST FROM………..
Iteration 2:
NODE SHORTEST COST FROM………..
Iteration 3:
NODE SHORTEST COST FROM………..
Iteration 4:
NODE SHORTEST COST FROM………..
Question.4:
The figure above shows a network of roads. The number on each arc represents the length of that
road in km.
(a) Use Dijkstra’s algorithm to find the shortest route from A to J.State your
shortest route and its length.
(b) Explain how you determine the shortest route from your labeled diagram.
The road from C to F will be closed next week for repairs.
(c) Find a shortest route from A to J that does not include C F and state its length.
Question.5:
The diagram above shows a network of cycle tracks with in a national park. The number on
each arc represents the time taken, in minutes, to cycle along the corresponding track.
(a) Use Dijkstra’s algorithm to find the quickest route from S to T. State your quickest route
and the time it takes.
(d).Explain how you determined your quickest route from labeled diagram
(d) Write down the quickest route from E to T.
Question.6:
[The total weight of the network is 167]
The diagram above represents a network of paths. The number on each arc gives the
time, in minutes, to travel along that path.
(a) Use Dijkstra’s algorithm to find the quickest route from A to H.State your quickest route
and the time taken.
Kevin must walk along each path at least once and return to his starting point.
(e) UseanappropriatealgorithmtofindthetimeofKevin’squickestpossibleroute,
starting and finishing at A. You should make your method and working clear.
Question.7:
Consider the following network.
Suppose that it uses flooding as the routing algorithm. If a packet sent by A to D has a maximum hop count
of 3, list all the routes it will take. Also tell how many hops worth of bandwidth it consumes.
Solution:
Question.8:
Consider the following network. Suppose that it uses flooding as the routing algorithm. If a packet sent by A
to G has a maximum hop count of 3, list all the routes it will take. Also tell how many hops worth of
bandwidth it consumes.
Solution:
Question.9:
Consider the following subnet. Distance vector routing is used, and the following vectors have just come in to
router C: from B: (5, 0, 8, 12, 6, 2); from D: (16, 12, 6, 0, 9, 10); and from E: (7, 6, 3, 9, 0, 4). The measured
delays to B, D, and E, are 6, 3, and 5, respectively. What is C’s new routing table? Give both the outgoing line
to use and the expected delay.
Solution:
Question.10:
Looking at the following subnet, how many packets are generated by a broadcast from B, using a) reverse
path forwarding and b) the sink tree? Sketch diagrams.
Solution:
