6.2.5 Complexity of Algorithms
A natural question to ask at this point is the following: Which one of the two shortest-path algorithms that we have described is better for computing the shortest paths between all possible pairs4 of nodes on a
6.2.5 Complexity of Algorithms
A natural question to ask at this point is the following: Which one of the two shortest-path algorithms that we have described is better for computing the shortest paths between all possible pairs4 of nodes on a network? To answer this question, a brief discussion of the subject of algorithmic complexity is first in order. The "goodness" of an algorithm is described in good part by its complexity.
The complexity of an algorithm is most often measured through the number of elementary operations that the algorithm requires to arrive at an answer under "worst-case conditions." An elementary operation is any one of the arithmetic operations (addition, subtraction, multiplication, division) or a comparison between two numbers or the execution of a branching instruc