Dijkstra’s algorithm, for finding the least-cost path from a specified node s to a specified node t, can be expressed in the following program:

for n := 1 to N do begin L[n] := ∞; final[n] := false; {all nodes are temporarily labeled with ∞}

pred[n] := 1 end;

L[s] := 0; final[s] := true; {node s is permanently labeled with 0}

recent := s; {the most recent node to be permanently labeled is s}

path := true;

{initialization over }

while final[t] = false do begin for n := 1 to N do {find new label}

if (w[recent, n] < ∞) AND (NOT final[n]) then

{for every immediate successor of recent that is not permanently labeled, do }

begin {update temporary labels}

newlabel := L[recent] + w[recent,n];

if newlabel < L[n] then begin L[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 := ∞;

for x := 1 to N do {find node with smallest temporary label}

if (NOT final[x]) AND (L[x] < temp) then begin y := x; temp :=L[x] end;

if temp < ∞ then {there is a path} then begin final[y] := true; recent := y end

{y, the next closest node to s gets permanently labeled}

else begin path := false; final[t] := true end end In this program, each node is assigned a temporary 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. 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.