Shortest-path routing: Bellman–Ford algorithm In this problem, we use the network topology in Figure 8.29 to illustrate the Bellman–Ford algorithm for finding the shortest route to a node. In the figure, the number beside a node serves as the label for the node, and the number near an arc indicates the length of the arc. For instance, the arc connecting node 1 and 2 has length 1. Define dij to be the length of the direct arc connecting nodes i and j. If there is no direct arc connecting the two nodes, we set dij¼1. By doing this, dij has meaning for any pair of nodes i and j in the network.

Consider node 1 as the destination node. The shortest path from node i to node 1 that traverses at most h arcs and goes through node 1 only once is called a shortest ( h) walk, and its length is denoted by Dhi

. Note there are two special cases. If all paths between node i and 1 consist of more than h arcs, Dhi

¼ 1. By convention, Dh1¼ 0 for any h.

(a) Determine D0i for i¼1, 2, . . . , 6. Find dij for all possible i, j¼1, 2, . . . , 6.

(b) The following iteration is used to generate the subsequent shortest walks.

Dhþ1 i ¼ min j

½dij þ Dh j for all i 6¼ 1:

Determine D1i for i 6¼ 1.

A B E

D C G H

F Figure 8.28 Flooding in network.

(c) Use the iteration equation in

(b) to compute D2i ;D3i ; . . . for i 6¼ 1. Stop the iteration when Dhþ1 i ¼ Dh i ; for all i 6¼ 1:
The minimum distance from node i to node 1 is Dhi in the last iteration.

10 5 3 1 4 1 3 Figure 8.29 A simple network.