Appendix A:

Shortest Path
Algorithms

A.l INTRODUCTION

In this appendix, the Bellman-Ford algorithm and the Floyd-Warshall algo-

rithm shortest path algorithms are described. These algorithms can be used
to solve several problems in VLSI signal processing such as computing the
iteration bound of recursive DFGs (see Chapter 2), retiming (see Chapter 4),
and retiming for folding (see Chapter 6).
The level of detail included here is intended to be enough so that the reader
can use these algorithms to solve the problems mentioned above. The theory
behind these algorithms has been omitted; however, for the interested reader,
there is a reference that discusses the theory behind these algorithms (e.g.,
(1], (2]).
The concepts of shortest paths and negative cycles are demonstrated using
the DFG in Figure A.l. The length of a path is the sum of the weights on
the edges of the path. The path 2 -t 3 -t 4 has length 1 + 2 = 3. There are
2 paths from node 2 to node 4, namely the path 2 -t 4 with length 1 and the
path 2 -t 3 -t 4 with length 3. The shortest path from node 2 to node 4 is
min{l, 3} = 1. A negative cycle in a directed graph is a directed cycle such
that the sum of the lengths on the edges of the cycle is negative. Figure A.1

717
718 SHORTEST PATH ALGORITHMS

Fig. A.l A graph containing 1 negative cycle.

contains the 2 cycles 2 -+ 4-+ 1 -+ 2 and 2 -+ 3 -+ 4 -+ 1 -+ 2. The cycle

2 -+ 4 -+ 1 -+ 2 is a negative cycle because the sum of the edge weights is
1 + 1 + (-3) = -1. The other cycle, 2 -+ 3 -+ 4 -+ 1 -+ 2, is not a negative
cycle because the sum of the edge weights is 1 + 2 + 1 + (-3) = 1. With this
in mind, each of the 2 shortest path algorithms works as follows. If there are
no negative cycles in the graph, the algorithm returns TRUE and provides
some information about the lengths of the shortest path between the nodes
(the amount of information varies between the two algorithms, as we will see
in the following sections). If there exists at least 1 negative cycle in the graph,
the algorithm returns FALSE. To summarize, each of the algorithms searches
for a negative cycle and provides shortest path information if no negative cycle
exists.
The following assumptions and notation are used. We assume that no
parallel edges exist in the graph, i.e., for 2 nodes U and V, there is at most 1
edge from U to V (U 4 V) and at most 1 edge from V to U (V 4 U). Let

w(U 4 V) = { the length of the edge U 4 V, if U 4.V exists ,

oo, otherw1se

where the length of the edge is simply a number associated with the edge.
Let n be the number of nodes in the graph, and assume that the n nodes are
numbered 1, 2, ... , n. The shortest path from the node U to the node V is
denoted as Suv.

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
 THE BELLMAN-FORD ALGORITHM 719

1, r< 1 l(U)=O
2. For k = 1 to n
3. Jfk #u
4. r< 1 >(k) = w(U 4 k)
5. For k = 1 to n - 2
6. For V = 1 to n
7. r(k+l) (V) = r(k) (V)
8. For W = 1 to n
9. If r<k+l) (V) > r<k> (W) + w(W 4 V)
10. r<k+l) (V) = r<k> (W) + w(W 4 V)
11. For V = 1 to n
12. For W = 1 to n
13. Ifr(n-l)(V) > r(n-l)(W) + w(W 4 V)
14. return FALSE and exit
15. return TRUE and exit

Fig. A.2 The Bellman-Ford algorithm.

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

are each of size n x 1, as described in Figure A.2. Note that r(k) (U) represents
the U-th entry in the column vector r(k).
If TRUE is returned, then r(n-l) (V) is Suv, 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) fork = 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( 3 ) (V) is the shortest path from node 2 to node V
for V = 1,2,3,4. •
720 SHORTEST PATH ALGORITHMS

Table A.l Values of r(k)(V) fork= 1, 2, 3 and V = 1, 2, 3, 4 from Example A.2.1

rlk) (V) k=1 k=2 k=3

V=1 00 3 3
V=2 0 0 0
V=3 1 1 1
V=4 2 2 2

Table A.2 Values of r(k) (V) for k = 1, 2, 3 and V = 1, 2, 3, 4 from Example A.2.2

rlk) (V) k=1 k=2 k=3

V= 1 00 2 2
V=2 0 0 -1
V=3 1 1 1
V=4 1 1 1

Example A.2.2 In this example, the Bellman-Ford algorithm is used to find

the shortest path from the origin U = 2 to the nodes in the graph in Figure A .1.
The values of r(k) (V) fork = 1, 2, 3 and V = 1, 2, 3, 4 are shown in Table A.2.
In this example, the Bellman-Ford algorithm returns FALSE because r< 3 ) (3) >
r< 3l (2) + w(2 4 3), so a negative cycle is detected. This negative cycle can be
seen in Figure A .1, where the cycle 2 -t 4 -t 1 -t 2 has length 1 + 1 - 3 = -1 .
•
A.J THE FLOYD-WARSHALL ALGORITHM

The Floyd-Warshall algorithm is an all-points shortest path algorithm. If

no negative cycles exist in the graph, the algorithm finds the shortest path
between all possible pairs of nodes in the graph. The algorithm constructs
n + 1 matrices R(k), k = 1, 2, ... , n + 1, which are each of size n x n, as
described in Figure A.4.
If TRUE is returned, then r< n+l) ( U, V) is Suv, which is the shortest path
from the node U to the node V. If FALSE is returned, then the graph contains
a negative cycle.

Example A.3.1 In this example, the Floyd- Warshall algorithm in Figure A.4
is used to solve the all-pairs shortest path problem for the graph in Figure A.3.
The values of r(k) (U, V) for U, V E {1, 2, 3, 4} and k = 1, 2, 3, 4, 5 are given
in Table A.3, where r(k) (U, V) is the element U, V in the matrix R(k). The
 COMPUTATIONAL COMPLEXITIES 721

1. For V = 1 to n
2. For U = 1 to n
3. r(ll(U, V) = w(U 4 V)
4. Fork= 1 ton
5. For V = 1 to n
6. For U = 1 to n
7. r(k+l)(U, V) = r(k)(U, V)
8. If r<k+t)(U, V) > r<kl(U, k) + r(k)(k, V)
9. r<k+t)(U, V) = r<kl(U,k) +r(k)(k, V)
10. For k = 1 to n
11. For U = 1 to n
12. If r<kl(U, U) < 0
13. return FALSE and exit
14. return TRUE and exit

Fig. A.4 The Floyd-Warshall algorithm.

Floyd- Warshall algorithm returns TRUE because all of the diagonal elements
in the matrices R(k), k = 1, 2, 3, 4, are nonnegative, so r( 5 ) (U, V) is the short-
est path from the node U to the node V. •

Example A.3.2 In this example, the Floyd- Warshall algorithm is used to

solve the all-pairs shortest path problem for the graph in Figure A.1. The
values of r(k)(U, V) for U, V E {1,2,3,4} and k = 1,2,3,4,5 are given in
Table A.4, where r(k) (U, V) is the element U, V in the matrix R(k). The Floyd-
Warshall algorithm returns FALSE because some of the diagonal elements in
the matrices R(k), k = 3, 4 and 5, are negative. Therefore, the graph contains
a negative cycle. •

A.4 COMPUTATIONAL COMPLEXITIES

The Bellman-Ford algorithm detects negative cycles and solves the single-
source shortest path problem if no negative cycles exist in O(n 3 ) time, while
the Floyd-Warshall algorithm detects negative cycles and solves the all-pairs
shortest path problem if no negative cycles exist in 0( n 3 ) time. The Bellman-
Ford algorithm requires O(n 4 ) time to solve the all-pairs shortest path prob-
lem since it needs to be run once for each of the n nodes. The Floyd-Warshall
algorithm is preferred for applications that require all-pairs shortest path so-
lution, and the Bellman-Ford algorithm and Floyd-Warshall algorithm can
be used interchangeably for applications that require a single-source shortest
path solution.
Modifications to the Bellman-Ford algorithm and early exit conditions for
both algorithms can be utilized to improve computational efficiency. The
 722 SHORTEST PATH ALGORITHMS

Table A.3 Values of r(k)(U, V) for Example A.3.1

R(ll R(2) R(3)

[~ ~ ~ ~J [: ~ ~ ~J [:
-3 -2
00 1
0000 2 00 0000 2 00 00 00
00 00 00 1 -2 00 00 1 -2 -1
R(4) R(s

[~ ~ ~ -~] uJJ
Table A.4 Values of r(k)(U, V) for Example A.3.2

R(l) R(2) R(3)

[~ ]] [~
-3

]] J~
-3

-~]
00 00 -3 -2
00 1 00 1 00 1
00 00 00 00 00 00
00 00 -2 00 -2 -1 -1
R(4)

[~
-3 -2
00
00
1

-2 -1 -1
00
-~] [-~ -4 -3
-1
0
0
1
-3 -2 -2
-~]
interested reader can find these details in [1].

REFERENCES

1. E. L. Lawler, Combinatorial Optimization: Networks and Matriods. Rinehart

and Winston, 1976.
2. T. H. Cormen, C. E. Leiserson and R. C. Rivest, Introduction to Algorithms,
MIT Press, 1990.