## Floyd-Warshall method

Another method to compute the shortest paths between all node pairs is from Floyd and Warshall with a computational complexity of O(N3). In this method, udefines the length of the shortest path from node i to j such that it does not pass through nodes numbered greater than m — 1 except nodes i and j. Then

1

uii = a

and

П+1 |

u |

= min{u",u" + umm]}

ufj+1 is the shortest path length matrix. Also, um+1 = 0 for all i and for all m.

This procedure has N(N — 1)(N — 2) equations, each of which can be solved by using N(N — 1)(N — 2) the additions and N(N — 1)(N — 2) comparisons. This order of complexity is the same as that for Bellman’s method (also known as the Bellman-Ford method as it was independently discovered by two researchers), which yields the shortest path only from a single origin. The Dijkstra method can also be applied N times, once from each source node, to compute the same shortest path length matrix. This process takes only N(N — 1)/2 additions for each pass, for a total of N2(N — 1)/2 additions, but again housekeeping functions in Dijkstra’s method make it noncompetitive.

The computation in the Floyd-Warshall method proceeds with u1 = A and Um+1 is obtained from Um by using row m and column m in Um to revise the remaining elements. That is, uij is compared with uim + umj and is replaced if the latter is smaller. Thus, the computation can be performed in place and is demonstrated in the following for the graph in Fig. 6a.

/ 0 |
100 |
40 |
30 |
ж |
0 |
100 |
40 |
30 |
ж |
0 |
100 |
40 |
30 |
120 |
||

100 |
0 |
ж |
ж |
20 |
100 |
0 |
140 |
130 |
20 |
100 |
0 |
140 |
130 |
20 |
||

40 |
ж |
0 |
20 |
30 |
А1 = |
40 |
140 |
0 |
20 |
30 |
А2 = |
40 |
140 |
0 |
20 |
30 |

30 |
ж |
20 |
0 |
ж 0 |
30 |
130 |
20 |
0 |
ж 0 |
30 |
130 |
20 |
0 |
ж |
||

оо |
20 |
30 |
00 |
V 00 |
20 |
30 |
00 |
120 |
20 |
30 |
00 |
0 |

A = |

0 |
100 |
40 |
30 |
70 |
0 |
100 |
40 |
30 |
70 |
0 |
90 |
40 |
30 |
70 |
||

100 |
0 |
140 |
130 |
20 |
100 |
0 |
140 |
130 |
20 |
90 |
0 |
50 |
70 |
20 |
||

40 |
140 |
0 |
20 |
30 |
А4 = |
40 |
140 |
0 |
20 |
30 |
А5 = |
40 |
50 |
0 |
20 |
30 |

30 |
130 |
20 |
0 |
50 |
30 |
130 |
20 |
0 |
50 |
30 |
70 |
20 |
0 |
50 |
||

70 |
20 |
30 |
50 |
0 |
70 |
20 |
30 |
50 |
0 |
70 |
20 |
30 |
50 |
0 |

A = |

Multiple Shortest Paths

Many times it is useful to be able to compute additional shortest paths between a node pair, which may be longer than the first shortest path but still short in case the first shortest path is not available. The first path may be congested or may have a failed link or a node. The problem can be constrained by specific requirements such as allowing

or not allowing repeated nodes and links or specific nodes and/or links. Specific methods exist to compute alternative shortest paths for all cases (see reference 14). One specific case with respect to fault tolerance is nonavailability of a node or a link. Such a path can be computed by removing the specific node or link in the original graph (removal of a node also removes all associated links) and then using the same shortest path algorithm. In another scenario, we may want another path that is mutually exclusive of the first path. In that case, all nodes and links have to be removed from the original graph before computing another shortest path. The algorithm to be used in these cases is the same as already stated.

## Добавить комментарий