Floyd-Warshall method

Another method to compute the shortest paths between all node pairs is from Floyd and Warshall with a computa­tional 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 discov­ered 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 com­pute 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 pro­ceeds with u1 = A and Um+1 is obtained from Um by us­ing row m and column m in Um to revise the remaining elements. That is, uij is compared with uim + umj and is re­placed 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 con­gested 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.

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

Ваш e-mail не будет опубликован. Обязательные поля помечены *