Subject: PS5 Problem 3
From: Rajmohan Rajaraman (rraj@ccs.neu.edu)
Date: Mon Dec 03 2001 - 23:30:51 EST
Problem 3 of PS5 has a few typos. Here is the problem restated after
corrections. (Basically, it was confusing whether there was a single
source or a single destination; as stated below, there is a single
destination d in the problem.)
Let T be a shortest path tree from all nodes an n-node network to a
given destination node d, and let (x,y) denote a link in T. Suppose
the Bellman-Ford algorithm for computing shortest paths to d starts
with the initial distance values D_i as follows: If the path from i to
d in T does not include (x,y), then D_i equals the true shortest path
distance from i to d; otherwise, D_i equals infinity. Show that the
Bellman-Ford algorithm converges to the shortest path distances from
all nodes to d in at most n iterations.
Rajmohan.
This archive was generated by hypermail 2b28 : Mon Dec 03 2001 - 23:31:57 EST