Floyd-Warshall Algorithm

Preview

1. What is the primary purpose of the Floyd-Warshall algorithm?
2. How is the Floyd-Warshall algorithm different from other shortest path algorithms such as Dijkstra’s algorithm?
3. Can the Floyd-Warshall algorithm be used to detect negative cycles in a graph? If yes, how?
4. What is the time complexity of the Floyd-Warshall algorithm and how does it differ from other shortest path algorithms?
5. In which types of applications is the Floyd-Warshall algorithm commonly used and why?

Explain

The Floyd-Warshall Algorithm is an efficient algorithm used to find the shortest path between all pairs of vertices in a weighted graph. It works by considering all possible intermediate vertices in a path, along with their combination so as to find the shortest distance path between every pair of vertices.

Let’s consider the following example to demonstrate the Floyd-Warshall Algorithm:

Suppose we have the following graph with its edge weights:

           3 
    (0)------->(3) 
    |         /|\ 
  2 |          | 
    |          | 1 
   \|/         | 
    (2)<-------(1) 
          10

The matrix of the shortest path distances between each pair of vertices can be initialized as follows:

   0       1      2        3
0  0       Inf    Inf     3
1  Inf     0      10      Inf
2  Inf     2      0       Inf
3  Inf     Inf    Inf      0

Here Inf represents an infinite distance between two vertices that are not connected by an edge.

Now, we apply the Floyd-Warshall Algorithm to find the shortest distance between all pairs of vertices in the graph.

We update each entry in this matrix using the following formula:

distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])

where i, j, and k are integers, and distance[i][j] represents the shortest distance between vertices i and j.

After applying the algorithm, we get the resulting matrix:

   0       1      2       3 
0  0       11     9       3 
1  Inf     0      10      14 
2  Inf     2      0       12 
3  Inf     Inf    Inf      0

As we can see, this matrix now contains the shortest distance between all pairs of vertices in the graph. For example, the shortest distance between vertices 0 and 1 is 11 and the shortest distance between vertices 2 and 3 is 12.

Keypoint

1. The Floyd-Warshall algorithm is used to find the shortest path between all pairs of vertices in a weighted graph.
2. It works by using dynamic programming, building a matrix of distances between all pairs of vertices.
3. The algorithm assumes that the graph does not contain negative-weight cycles.
4. The time complexity of the algorithm is O(n^3), where n is the number of vertices in the graph.
5. The algorithm can be used to determine whether or not a graph is strongly connected.
6. The algorithm can also be used to find the diameter of a graph, which is the maximum distance between any two vertices.
7. The Floyd-Warshall algorithm is commonly used in computer networking to find the shortest path between two hosts.

Review

1. What is the time complexity of Floyd-Warshall algorithm?
   Answer: The time complexity of Floyd-Warshall algorithm is O(n^3), where n is the number of vertices in the graph.

2. What is the minimum possible distance between two vertices in a graph using Floyd-Warshall algorithm?
   Answer: The minimum possible distance between two vertices using Floyd-Warshall algorithm is 0 if the vertices are the same, or the weight of the direct edge if there exists one, otherwise it is the sum of weights of the shortest path between them.

3. What is the optimal sequence of vertices in a path from ‘A’ to ‘B’ using Floyd-Warshall algorithm?
   Answer: Floyd-Warshall algorithm does not provide the sequence of vertices in a path. Rather, it provides the shortest distance between any two vertices in the graph.

4. What is the output of Floyd-Warshall algorithm when applied on a disconnected graph?
   Answer: The output of Floyd-Warshall algorithm on a disconnected graph is a matrix with infinite distances between disconnected vertices.

5. What is the advantage of using Floyd-Warshall algorithm over Dijkstra’s algorithm for finding shortest path in a graph?
   Answer: Floyd-Warshall algorithm can handle negative edges, while Dijkstra’s algorithm cannot. Additionally, Floyd-Warshall algorithm can find the shortest paths between all pairs of vertices in the graph in a single run, while Dijkstra’s algorithm requires multiple runs for each pair of vertices.