Floyd Warshall Algorithm

Learn the Floyd-Warshall Algorithm for solving the All-Pair Shortest Path problem using Dynamic Programming, with concept, pseudocode, advantages, and complexity analysis.

Floyd-Warshall Algorithm

Introduction

The All-Pair Shortest Path (APSP) problem aims to find the shortest paths between every pair of vertices in a given graph.

The Floyd-Warshall Algorithm is a well-known algorithm used to solve this problem efficiently.
It is based on the Dynamic Programming technique.

Concept of Floyd-Warshall Algorithm

The Floyd-Warshall Algorithm works on the idea that:

If the shortest path between two vertices i and j passes through an intermediate vertex k, then this path can be improved by considering k as an intermediate vertex.

At each step, the distance between vertices is updated using the formula:

dist[i][j]=min⁡(dist[i][j],  dist[i][k]+dist[k][j])dist[i][j] = \min(dist[i][j],\; dist[i][k] + dist[k][j])dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])

Reasons for Using Dynamic Programming

The Floyd-Warshall Algorithm satisfies both the properties required for Dynamic Programming:

• Overlapping Subproblems
  The same distance calculations are repeated multiple times.
• Optimal Substructure
  The shortest path between two vertices depends on the shortest paths of smaller subpaths.

Therefore, Dynamic Programming is effectively used in this algorithm.

Working Principle of the Algorithm

The working of the Floyd-Warshall Algorithm involves the following steps:

1. Create an initial distance matrix for the graph
2. If there is no direct edge between two vertices, the distance is set to ∞ (infinity)
3. Each vertex is considered as an intermediate vertex one by one
4. Distances between all vertex pairs are updated accordingly
5. After completion, the matrix contains the shortest distances between every pair of vertices

Floyd-Warshall Algorithm (Pseudocode)

FloydWarshall(dist, n)

for k = 1 to n                for i = 1 to n

        for j = 1 to n

            if dist[i][j] > dist[i][k] + dist[k][j]

                dist[i][j] = dist[i][k] + dist[k][j]

Example

Consider a graph with 4 vertices.
The graph is represented using an adjacency matrix.

After applying the F-W Algorithm, the distance matrix contains the shortest paths between all pairs of vertices.

Note: Floyd-Warshall always uses an adjacency matrix representation of the graph.

Time and Space Complexity

• Time Complexity: O(n3)O(n^3)O(n3)
• Space Complexity: O(n2)O(n^2)O(n2)

Advantages of F-W Algorithm

• Computes all-pair shortest paths using a single algorithm
• Can handle negative edge weights
• Simple and easy to implement
• Suitable for dense graphs

Limitations of F-W Algorithm

• Cannot be used for graphs containing negative weight cycles
• High time complexity makes it inefficient for very large graphs

Conclusion

The Floyd-Warshall Algorithm is an efficient and widely used algorithm based on Dynamic Programming.
It successfully finds the shortest paths between every pair of vertices in a graph.

Due to its simplicity and effectiveness, it is an important algorithm for solving All-Pair Shortest Path problems in computer science.

Some More: 

• POP- Introduction to Programming Using ‘C’
• DS – Data structure Using C
• OOP – Object Oriented Programming 
• Java Programming
• DBMS – Database Management System
• RDBMS – Relational Database Management System
• https://defineinfoloop.blogspot.com/?m=1