Floyd's Algorithm

9 Key excerpts on "Floyd's Algorithm"

• 

  eBook - PDF

  Graphs, Algorithms, and Optimization

  • William Kocay, Donald L. Kreher(Authors)
  • 2016(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  2.7 Floyd’s algorithm Floyd’s algorithm solves the All Paths Problem, computing a matrix of values Dist [ u,v ] = D IST ( u,v ) , for all u,v ∈ V ( G ) . Initially, Dist [ · , · ] equals the weighted adjacency matrix A , where A [ u,v ] =    W T ( u,v ) , if u −→ v, ∞ , if u negationslash −→ v, 0 , if u = v. Floyd’s algorithm is extremely simple to program. procedure F LOYD ( Dist ) comment: Dist [ u,v ] will equal D IST ( u,v ) , upon completion for k ← 1 to n do    for v ← 1 to n − 1 do braceleftbigg for w ← v + 1 to n do Dist [ v,w ] ← MIN ( Dist [ v,w ] , Dist [ v,u k ] + Dist [ u k ,w ]) The for-loops for v and w together examine ( n 2 ) pairs vw for each value of u , so the complexity of the algorithm is n parenleftbigg n 2 parenrightbigg = 1 2 n 3 − 1 2 n 2 = O ( n 3 ) . The graph is stored as a weighted adjacency matrix, in which non-adjacent ver-tices v,w can be considered to be joined by an edge of weight ∞ . Figure 2.9 shows a weighted graph on which the reader may like to work Floyd’s algorithm by hand. Let the vertices of G be named u 1 ,u 2 ,...,u n . In order to prove that Floyd’s algorithm works, we prove by induction, that at the end of k th iteration of the for-loop for u , Dist[ v,w ] is the length of the shortest vw -path which uses only vertices v,w , and u 1 ,u 2 ,...,u k . When k = 0 , that is, before the first iteration, Dist [ v,w ] is the length of the edge vw , that is, the length of the shortest path using only vertices v and w . At the end of the first iteration, Dist [ v,w ] = MIN ( W T ( v,w ) , W T ( v,u 1 ) + W T ( u 1 ,w )) . This is the length of the shortest vw -path using only vertices v,w , and 42 Graphs, Algorithms, and Optimization u 1 u 2 u 3 u 4 u 5 5 4 4 6 2 2 1 3 u 1 u 2 u 3 u 4 u 5 u 1 0 5 ∞ 3 2 u 2 5 0 4 ∞ 2 u 3 ∞ 4 0 1 4 u 4 3 ∞ 1 0 6 u 5 2 2 4 6 0 FIGURE 2.9 A complete weighted graph and its weighted adjacency matrix u 1 , because that path either uses u 1 , or else consists only of the edge vw .

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Graphs and Networks

  • S. R. Kingan(Author)
  • 2022(Publication Date)
  • Wiley

    (Publisher)

  Topics for Deeper Study 131 (I3’) For all weight functions 𝑤, the greedy algorithm produces a maximal member of  of maximum weight. 3 5.9 The Bellman-Ford Algorithm, which is based on separate algorithms by Bellman (1958) and Ford and Fulkerson (1962), solves the single source shortest path problem for weighted digraphs, where some of the arc weights may be negative. Review this algorithm in (Cormen et al., 2001). 5.10 Finding the distance between every pair of vertices is known as the “All Pairs Shortest Paths problem.” The Floyd-Warshall algorithm solves this problem for weighted graphs, where some of the edge weights may be neg- ative. This is used to find the diameter of the graph. Floyd (1962) developed this algorithm based on a theorem by Warshall (1962). Review this algo- rithm in (Cormen et al., 2001). 5.11 Suppose we assign a label to each vertex in a connected graph in such a way that, given a starting vertex and the label assigned to the ending vertex, a shortest path to the ending vertex can be found only by looking at the labels in the neighborhood of each successive vertex in the path. That is, as we are constructing a shortest path, at each step we should be able to choose the next vertex on the path simply by comparing the labels on the neighbors of the current vertex to the label on the destination. In Graham and Pollak (1971) and Graham and Pollak (1972), the authors showed that this can be done for any connected graph. The labels they developed are made up of the symbols “0”, “1” and “*”. The choice of the next vertex in a shortest path depends on the Hamming distance between the label on a neighbor- ing vertex and the label on the destination vertex. The Hamming distance between two lists of symbols of the same length is the number of positions in which the two lists differ. In this case, the symbols “0” and “1” are con- sidered different, but “0” and “*” are considered the same, as are “1” and “*”.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Data Structure Practice

  for Collegiate Programming Contests and Education

  • Yonghui Wu, Jiande Wang(Authors)
  • 2016(Publication Date)
  • CRC Press

    (Publisher)

  423 Chapter 13 Algorithms of Best Paths Given a weighted, directed graph G = ( V , E ), each edge is with a real-valued weight. The weight of path P = ( v 0 , v 1 , … , v k ) is the sum of weights of its constituent edges: w p w v v i i i k ( ) ( , ) = -= ∑ 1 1 The weight of the shortest path (longest path) from vertex u to vertex v is defined as follows: δ ( , ) min(max){ ( ) } u v w p u v p u p =  →  if there is a path from to v ∞      otherwise The best path from vertex u to vertex v is defined as any path with weight w ( p ) = δ ( u , v ). In this chapter, three kinds of algorithms are introduced: 1. The Warshall algorithm is used to get the transitive closure for a graph. 2. The Floyd–Warshall algorithm is used to get all-pairs best paths in a graph. 3. The Dijkstra algorithm, Bellman–Ford algorithm, and shortest path faster algorithm (SPFA) are used to get single-source shortest paths in a graph. 13.1 Warshall Algorithm and Floyd–Warshall Algorithm The Warshall algorithm is used to compute the transitive closure of a relation for a graph. Suppose relation R is represented by digraph G . All vertices in G are v 1 , v 2 , … , v n . The graph G ′ for the transitive closure t ( R ) can be obtained from G as follows. If there exists a path from vertex v i to vertex v j in G , then an arc from v i to v j is added in G ′ . The adjacency matrix A for G ′ is defined as follows. If there exists a path from vertex v i to vertex v j , then A [ i ][ j ] = 1, and vertex v j is reachable from vertex v i ; otherwise, A [ i ][ j ] = 0, and vertex v j isn’t reachable from vertex v i . That 424 ◾ Data Structure Practice: For Collegiate Programming Contests and Education is, computing the transitive closure of a relation is to determine whether every pair of vertices are reachable or not. It is a problem of transitive closure for a graph. Suppose there is a sequence of square matrices order n A (0) , … , A ( n ) , where each element in square matrices is 0 or 1.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Handbook of Graph Theory, Combinatorial Optimization, and Algorithms

  • Krishnaiyan "KT" Thulasiraman, Subramanian Arumugam, Andreas Brandstädt, Takao Nishizeki, Krishnaiyan "KT" Thulasiraman, Subramanian Arumugam, Andreas Brandstädt, Takao Nishizeki(Authors)
  • 2016(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  Now we discuss one of these algorithms. This algorithm, due to Floyd [57], is based on Warshall’s algorithm (Algorithm 2.5) for computing transitive closure. Consider an n -vertex directed graph G with lengths associated with its edges. Let the vertices of G be denoted as 1 , 2 , . . ., n . Assume that there are no negative-length directed circuits in G . Let W = [ w ij ] be the n × n matrix of direct lengths in G , that is, w ij is the length of the directed edge ( i, j ) in G . We set w ij = ∞ if there is no edge ( i, j ) directed from i to j . We also set w ii = 0 for all i . Starting with the matrix W (0) = W , Floyd’s algorithm constructs a sequence W (1) , W (2) , . . ., W ( n ) of n × n matrices so that the entry w ( n ) ij in W ( n ) would give the distance from i to j in G . The matrix W ( k ) = [ w ( k ) ij ] is constructed from the matrix W ( k − 1) = [ w ( k − 1) ij ] according to the following rule: w ( k ) ij = min { w ( k − 1) ij , w ( k − 1) ik + w ( k − 1) kj } (2.14) Let P ( k ) ij denote a path of minimum length among all the directed i − j paths, which use as internal vertices only those from the set { 1 , 2 , . . ., k } . The following theorem proves the correctness of Floyd’s algorithm. Theorem 2.13 For 0 ≤ k ≤ n , w ( k ) ij is equal to the length of P ( k ) ij . Proof . Proof follows from the following observations. 1. If P ( k ) ij does not contain vertex k then w ( k ) ij = w ( k − 1) ij . 2. If P ( k ) ij contains vertex k then w ( k ) ij = w ( k − 1) ik + w ( k − 1) kj because a subpath of a shortest path is a shortest path between the end vertices of the subpath. Note: See the similarity between the proof of this theorem and the proof of correctness of Warshall’s algorithm for transitive closure. Usually, in addition to the shortest lengths, we are also interested in obtaining the paths that have these lengths. Recall that in Dijkstra’s algorithm we use the PRED array to keep a

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  An Elementary Approach to Design and Analysis of Algorithms

  • Lekh Raj Vermani, Shalini Vermani(Authors)
  • 2019(Publication Date)
  • WSPC (EUROPE)

    (Publisher)

  k–1. Hence

  Therefore, we finally have, for k ≥ 1,

  When k = 0,

  For k = 0, 1, 2, . . . , n, we define

  Since no intermediate vertex from i to j can be larger than n, the entries of D

  n

  give the shortest path lengths between every pair of vertices of G.

  The procedure described is known as Floyd–Warshall algorithm. We formalize this in the following algorithm.

  Algorithm 10.2. Floyd–Warshall Algorithm for Shortest Path Lengths G(V, E), w

  1.G = (V, E) is a weighted directed graph, w the weight function associating a real number to every edge of G, G has no negative weight cycle, V = {1, 2, . . . , n}

  2.initially d

  ij

  0 = w(i, j) if there is an edge from i to j, d

  ij

  0 = ∞ otherwise

  3.d

  ii

  0 = 0

  4.for k = 1 to n

  5.for i = 1 to n

  6.for j = 1 to n

  7.d

  ij

  k

  = min{d

  ij

  k–1

  , d

  ik

  k–1

  + d

  kj

  k–1

  }

  8.return D

  n

  The for loop in steps 4 to 7 computes d

  ij

  k

  in 2n3 computations as for a given k, d

  ij

  k

  is computed from d

  ij

  k–1

  by one addition and one comparison. As i, j both take values from 1 to n, the number of computations involved is 2n2 . As k takes values from 1 to n, the total number of computations is 2n2 × n = 2n3 . Hence the running time of this algorithm is O(n3 ) which is far better than the running time O(n4 ) of the recursive algorithm and the running time O(n3 lg n) of the revised recursive algorithm considered in the last section. For this reason the recursive and revised recursive algorithms considered there are called slow algorithms.

  We now use Floyd–Warshall algorithm to find the shortest path lengths for the pair of vertices in the graph G of Example 10.1.

  Example 10.2. Find the shortest path lengths for all the pairs of vertices of the graph G given in Fig. 10.1 .

  Solution. Here

  Now

  Therefore, the matrices D

  k

  are as given below:

  The shortest path lengths between the pairs of vertices of G are then given by the entries of the matrix D5 . Observe that D5 is the same as the matrix L(4)

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Simulation for Applied Graph Theory Using Visual C++

  • Shaharuddin Salleh, Zuraida Abal Abas(Authors)
  • 2016(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  Consider α ij as the shortest path between ( v i , v j ) for i , j = 1, 2,…, n . The intermediate nodes between them are ( v 1 , v 2 ,…, v k ). If v k is an intermediate node, then α α α ij k ik k kj k ( ) ( ) ( ) = + --1 1 ; otherwise, α α ij k ij k ( ) ( ) = -1 . That gives α α α α ij k ij k ik k kj k ( ) ( ) ( ) ( ) min , = + ( 29 ---1 1 1 in the case of k > 0 and α ij ij w ( ) 0 = for k = 0. The idea summarizes the algorithm as follows: Given: The graph G ( V , E ) and weight matrix W = [ w ij ] for i , j = 1, 2,…, n . Initialization: D w ij ij =     = α ( ) [ ] 0 . Process: For k = 1 to n For i = 1 to n For j = 1 to n Compute α α α α ij k ij k ik k kj k ( ) ( ) ( ) ( ) min , = + ( 29 ---1 1 1 Endfor Endfor Endfor Output: D SP v v i j ij k = = ( , ) ( ) α for i , j = 1, 2,…, n . The final matrix of D SP v v i j ij k = = ( , ) ( ) α stores the shortest paths of all the pairs of nodes. Floyd-Warshall’s algorithm differs from Dijkstra’s algorithm in that the shortest paths between all pairs of nodes in the former are computed using a single nested loop. Dijkstra’s algorithm can also be used to compute the shortest paths of all pairs of nodes but this is done by calling Dijkstra() in Code 4 A n times, which may be quite tedious and not practical. One practical application of Floyd-Warshall’s algorithm is finding the transitive closure of a directed graph. In this problem, the idea is to construct a matrix for the reachability 102 Simulation for Applied Graph Theory Using Visual C++ of the paths from v i to v j where the solution is already described in Floyd-Warshall’s algo-rithm. The matrix is obtained by replacing the weights between the pairs of nodes with the binary values of 1 if the directed edge exists and 0 otherwise. 4.3.1 Code 4 B : Implementing Floyd-Warshall’s Algorithm Code 4 B is the implementation of Floyd-Warshall’s algorithm for finding the shortest paths between all pairs of nodes in the weighted graph G ( V , E ) for n = | V | = 20.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Optimization Algorithms for Networks and Graphs

  • James Evans(Author)
  • 2017(Publication Date)
  • CRC Press

    (Publisher)

  The preceding sections considered the problem of finding various shortest paths. Often, however, knowledge of the second, third, fourth, etc., shortest paths between two vertices is useful. For example, an airline might want to know the runner-up shortest flight routes between Springfield and Ankara in case one of its clients could not take the shortest flight route due to visa difficulties, flight cancellations, or airline strikes along the shortest flight route.

  This section first presents an algorithm, called the double-sweep algorithm, that finds the k shortest path lengths between a specified vertex and all other vertices in the graph. Next, this section presents two algorithms, called the generalized Floyd algorithm and the generalized Dantzig algorithm, that find the k shortest path lengths between every pair of vertices in the graph.

  The Dijkstra, Floyd, and Dantzig algorithms were able to construct various shortest paths. These algorithms essentially consisted of performing a sequence of two arithmetic operations, addition and minimization. These two operations were performed on single numbers that represented either arc lengths or path lengths. For example, equation (1) , which defines the Dijkstra algorithm, consists exclusively of addition and minimization. The same is true for equation (3) , which defines the Floyd algorithm, and equations (4) −(7), which define the Dantzig algorithm.

  The algorithms to be presented in this section (double-sweep algorithm, generalized Floyd algorithm, and generalized Dantzig algorithm) also consist exclusively of addition and minimization operations. However, these operations are performed not on single numbers (as with the previous algorithms) but on sets of k distinct numbers that represent the lengths of paths or arcs. With this as motivation, let

  Rk

  denote the set of all vectors (d 1 , d 2 ,

  …, dk

  ) with the property that d 1 < d 2

  < … < dk .

  † Thus, the components of a member of

  Rk

  are distinct and arranged in ascending order. For example, ( − 3, − 1, 0, 4, 27) ∈

  R5 .

  Let a = (a 1 , a 2 ,

  … , ak

  ) and b = (b 1 , b 2 ,

  …, bk

  ) be two members of

  Rk

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Algorithm Design and Applications

  • Michael T. Goodrich, Roberto Tamassia(Authors)
  • 2014(Publication Date)
  • Wiley

    (Publisher)

  In the worst case, this bound could be as large as O(n 3 log n). Likewise, if  G contains no negative-weight cycles, then we could run the Bellman-Ford algorithm starting from each vertex in  G in turn. This approach would run in O(n 2 m) time, which, in the worst case, could be as large as O(n 4 ). In this section, we consider algorithms for solving the all-pairs shortest path problem in O(n 3 ) time, even if the digraph contains negative-weight edges (but not negative-weight cycles). 14.5.1 A Dynamic Programming Shortest-Path Algorithm The first all-pairs shortest-path algorithm we discuss is a variation on an algorithm we have given earlier in this book, namely, the Floyd-Warshall algorithm for com- puting the transitive closure of a directed graph (Algorithm 13.13). Let  G be a given weighted directed graph. We number the vertices of  G arbitrar- ily as (v 1 , v 2 , . . . , v n ). As in any dynamic programming algorithm (Chapter 12), the key construct in the algorithm is to define a parametrized cost function that is easy to compute and also allows us to ultimately compute a final solution. In this case, we use the cost function, D k i,j , which is defined as the distance from v i to v j using only intermediate vertices in the set {v 1 , v 2 , . . . , v k }. Initially, D 0 i,j = ⎧ ⎨ ⎩ 0 if i = j w((v i , v j )) if (v i , v j ) is an edge in  G +∞ otherwise. Given this parametrized cost function D k i,j , and its initial value D 0 i,j , we can then easily define the value for an arbitrary k > 0 as D k i,j = min{D k−1 i,j , D k−1 i,k + D k−1 k,j }. In other words, the cost for going from v i to v j using vertices numbered 1 through k is equal to the shorter of two possible paths. The first path is simply the shortest path from v i to v j using vertices numbered 1 through k − 1.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Algorithms and Theory of Computation Handbook, Volume 1

  General Concepts and Techniques

  • Mikhail J. Atallah, Marina Blanton(Authors)
  • 2009(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  For example, in the bottleneck shortest path problem, the objective is to find, for each vertex v , a path from the root to v in which the length of the longest edge in that path is minimized. A small change to Dijkstra’s algorithm (replacing the operation + in R ELAX by max) solves this problem. Other problems that can be solved by suitably modifying Dijkstra’s algorithm include the following: • Finding most reliable paths from the root to every vertex in a graph where each edge is given a probability of failure (independent of the other edges) • Finding the fastest way to get from a given point in a city to a specified location using public transportation, given the train/bus schedules 7.6.5 Bellman–Ford Algorithm The shortest path algorithm described above directly generalizes to directed graphs, but it does not work if the graph has edges of negative length. For graphs that have edges of negative length, but no cycles of negative length, there is a different algorithm solves due to Bellman and Ford that solves the single-source shortest paths problem in O ( | V || E | ) time. In a single scan of the edges, the R ELAX operation is executed on each edge. The scan is then repeated | V | − 1 times. No special data structures are required to implement this algorithm, and the proof relies on the fact that a shortest path is simple and contains at most | V | − 1 edges. This problem also finds applications in finding a feasible solution to a system of linear equations of a special form that arises in real-time applications: each equation specifies a bound on the difference Basic Graph Algorithms 7 -15 between two variables. Each constraint is modeled by an edge in a suitably defined directed graph. Shortest paths from the root of this graph capture feasible solutions to the system of equations (for more information, see [7, Chapter 24.5]).

  Sign up to read

  Learn more about book