ØThe well known
``Warshall's algorithm'‘ determines for each i, j ⊂ N whether there is a path from node i to node j by computing a Boolean
matrix, the transitive closure of the graph's adjacency matrix, in less
than n3Boolean operations.
Øor
Ø
ØFloyd's algorithm extends
Warshall's algorithm to obtain the cost of the ``smallest cost path''
between any pair of vertices in the form of a real-valued matrix.
Øor
Ø
ØIf the QoS metric is
additive then we can use the Floyd-Warshall algorithm to get the smallest value of
the QoS metric among all known paths from any node i to any node j.
ØFor non-additive metrics
we have developed a generalisation of the Floyd-Warshall, which is
described next.