Subject: comments on Problem 3 of PS5
From: Rajmohan Rajaraman (rraj@ccs.neu.edu)
Date: Wed Dec 05 2001 - 14:18:12 EST
Some students have raised the following question (or something in the
same spirit) regarding Problem 3 of PS5.
"If the shortest path tree T is already given, then why do we have to
compute the shortest paths?"
We do not have the shortest path tree T. The shortest path tree has
been mentioned only to describe what the initial estimates of the
distance values are. A general motivation for the problem -- which is
not needed for solving the problem :-) -- is as follows.
Suppose all nodes have calculated the shortest path distances to
destination d. Now the weight of an edge e -- which is on some
shortest path -- changes. Then one solution is to continue the
Bellman-Ford algorithm from the current estimates (which may be wrong)
and let the distance estimates converge to the correct values. As we
have seen in class, however, it may take a long time for convergence.
This was the "bad news phenomenon" or the "count-to-infinity" problem
discussed in class.
A different solution is for the node at the head of the link e to send
a distance estimate of infinity to nodes "away from the link e" and
let this estimate propagate quickly to all the nodes whose shortest
path to d contains e. Once this has happened, the distance estimates
of all of these nodes will be infinity, while that for the other nodes
(whose shortest paths to d do not contain e) will the correct values.
Now, we continue with Bellman-Ford. And the claim is that within n
iterations, we will converge to the shortest path values for all
nodes. This is similar to what we have to show in Problem 3.
Rajmohan.
This archive was generated by hypermail 2b28 : Wed Dec 05 2001 - 14:19:11 EST