Floyd-Warshall's Algorithm

From Algorithmist
Jump to navigation Jump to search

The Floyd-Warshall Algorithm is an efficient algorithm to find all-pairs shortest paths on a graph. That is, it is guaranteed to find the shortest path between every pair of vertices in a graph. The graph may have negative weight edges, but no negative weight cycles (for then the shortest path is undefined).

This algorithm can also be used to detect the presence of negative cycles—the graph has one if at the end of the algorithm, the distance from a vertex to itself is negative.

Algorithm[edit]

The Floyd-Warshall Algorithm is an application of Dynamic Programming.

Let be the the length of the shortest path from and that uses only the vertices as intermediate vertices. The following recurrence:

  • is our base case - is the length of the edge from vertex to vertex if it exists, and otherwise.
  • : For any vertex and vertex , the length of the shortest path from to with all intermediate vertices simply does not involve the vertex at all (in which case it is the same as ), or that the shorter path goes through vertex , so the shortest path between vertex and vertex is the combination of the path from vertex to , and from vertex to .

After iterations, there is no need anymore to go through any more intermediate vertices, so the distance represents the shortest distance between and .

Pseudocode[edit]

The pseudocode below assumes an input graph of N vertices.

for i = 1 to N
   for j = 1 to N
      if there is an edge from i to j
         dist[0][i][j] = the length of the edge from i to j
      else
         dist[0][i][j] = INFINITY
  
for k = 1 to N
   for i = 1 to N
      for j = 1 to N
         dist[k][i][j] = min(dist[k-1][i][j], dist[k-1][i][k] + dist[k-1][k][j])

This will give the shortest distances between any two nodes, from which shortest paths may be constructed.

This algorithm takes time and space, and has the distinct advantage of hiding a small constant in its behavior, since very little work is done in the innermost loop. Furthermore, the space-bound can be reduced further to by noticing that is independent from .

Implementation In C++[edit]

Floyd-Warshall's Algorithm.cpp


Implementation In C[edit]

C