Sometimes I hate the Internet for the very reason that it now
gives complete strangers a medium through which to waste my time.
I used to leave that job for my friends....
Adam
> From ao718@rgfn.epcc.edu Sun May 5 14:22:03 1996
> To: adam@cs.caltech.edu
> Reply-To: ao718@rgfn.epcc.edu
>
> Dear Mr. Rifkin,
>
> I was working as a Senior Scientific Officer at Thin Film Laboratory,
> Physics Department, IIT(Indian Institute of Technology)-Delhi after
> obtaining Ph.D from the same Institute. I came to USA to present two
> Research papers in an International Conference on Thin Films and
> Metallurgical Coatings which was held at San Diego, CA, last year.
> Presently I am learning computer programming particularly I am
> interested in Data Communication. I am facing problem with one algorithm
> which is meant to find the shortest path in computer network and packet
> switching. I am basically from physics background, hence NOT a expert in
> Algorithms. I would appreciate if you kindly help me to write the
> algorithm in Bellman-Ford form.
>
> Problem is this:
>
> s = source node
> N = set of nodes in the network
> M = set of nodes so far incorporated in the algorithm
> dij = link cost from node i to nodej
> Dn = cost of the least-cost path from node s to node n that is currently
> known to the algorithm
>
> Dijkstra's algorithm can be expressed in the following program:
>
> for n: = 1 to N do
> begin
> D[n]: = infinity(symbol); final[n]: = false;{all nodes are
> temporarily labeled with infinity}
>
> pred[n]: = -1
> end;
> D[s]: = 0; final[s]: = true; {node s is permanently labeled with 0}
> recent: = s;
> path: = true;
> {initialization over}
>
> 1 for n: = 1 to N do {find new label}
> if (d[recent, n] < infinity) AND (NOT final[n]) then
> {for every immediate successor of recent that is not permanently
> labeled, do}
> begin{update temporary labels}
> newlabel: = D[recent] + d[recent,n];
> if newlabel < D[n] then
> begin D[n]: = newlabel; pred[n]: recent end
> {relabel n if there is a shorter path via node
> recent and make
> recent the predecessor of n on the shortest path
> from s}
> end;
> temp: = infinity;
> for d: = 1 to N do { find node with smallest
> temporary label}
> if (NOT final[x] AND (D[x] < temp) then
> begin y: = x; temp: D[x] emd;
> if temp<infinity then { there is a path}
>
> begin final[y]: = true; recent:=y end
> {y, the next closest node to s gets permanently labeled}
>
> In this program, each node is assigned a temporarly label initially. As a
> final path to a node is determined, it is assigned a permanent label
> equal to the cost of the path from s.
>
> Please WRITE a similar program for the Bellman-Ford algorithm. Hint: The
> Bellman-Ford algorithm is often called a label-correcting method, in
> contrast to Dijkstra's label-setting method.
>
> THE ABOVE PROBLEM IS GIVEN IN PAGE 338, OF WILLIAM STALLINGS, 4TH
> EDITION.
>
> Hoping to receive your mail
>
> Sripathi Yarasi, Ph.D