VLSI Digital Signal Processing Systems: Design and Implementation

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 (n³) time, while the Floyd-Warshall algorithm detects negative cycles and solves the all-pairs shortest path problem if no negative cycles exist in (n³) time. The Bellman-Ford algorithm requires (n⁴) time to solve the all-pairs shortest path problem 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 solution, 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 interested reader can find these details in [1].

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

Table A.4    Values of r^(k) (U, V) for Example A.3.2