Computing the QoS matrices
Ø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 n3 Boolean 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.