VLSI Digital Signal Processing Systems: Design and Implementation

A.2    THE BELLMAN-FORD ALGORITHM

The Bellman-Ford algorithm is a single-point shortest path algorithm. If no negative cycles exist in the graph, it finds the shortest path from an arbitrarily chosen node U (called the origin) to each node in the graph. For a graph with n nodes, the algorithm constructs n − 1 vectors r^(k), k = 1, 2, … , n − 1, which are each of size n × 1, as described in Figure A.2. Note that r^(k) (U) represents the U-th entry in the column vector r^(k).

Fig. A.2    The Bellman-Ford algorithm.

Fig. A.3    A graph containing no negative cycles.

If TRUE is returned, then r⁽ⁿ⁻¹⁾(V) is S_UV , which is the shortest path from the node U to the node V. If FALSE is returned, then the graph contains at least one negative cycle.

Example A.2.1  In this example, the Bellman-Ford algorithm in Figure A.2 is used to find the shortest path from the node U = 2 to the nodes in the graph in Figure A.3. The values of r^(k)(V) for k = 1, 2, 3 and V = 1, 2, 3, 4 are shown in Table A.1. The Bellman-Ford algorithm returns TRUE in this example, so the value of r⁽³⁾(V) is the shortest path from node 2 to node V for V = 1, 2, 3, 4.

Table A.1    Values of r^(k)(V) for k = 1, 2, 3 and V = 1, 2, ...