All-Pairs Shortest Paths

Idea Behind Floyd Warshall Algorithm:

The Floyd Warshall Algorithm is a classic algorithm used in computer science for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles). The algorithm is an example of dynamic programming and operates by systematically examining all possible paths between each pair of vertices and updating the shortest paths as it progresses. Here's the idea behind the Floyd Warshall Algorithm presented in a bulleted form:

Initialization:

• Start with a matrix representation of the graph, where the element at the ith row and jth column represents the cost or distance from the vertex i to vertex j. If there is no direct path from i to j, the distance is set to infinity (or a very large number).
• If a vertex has a path to itself, the distance is zero.
   

Iterative Updates:

• The algorithm iteratively updates the matrix to include the shortest possible paths between all pairs of vertices.
• It considers each vertex as an intermediate point that might be on the shortest path between any two vertices.
   

Dynamic Programming Principle:

• At each step of the algorithm, it considers paths that go through an intermediate set of vertices, with each step increasing the set of considered intermediates.
• The key formula used for updates is: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]), where k is the intermediate vertex being considered. This step checks if the path from i to j passing through k is shorter than the direct path from i to j.
   

Handling Negative Weights:

• The algorithm can handle graphs with negative edge weights, making it a versatile tool in situations where paths may have 'costs' or 'weights' that decrease overall path lengths.
• However, it does not work with graphs that contain negative cycles, as the concept of the "shortest path" becomes undefined.
   

Completeness:

• After considering all vertices as intermediate points, the final matrix represents the shortest distances between all pairs of vertices.
• If the final matrix has a negative number in the diagonal, it indicates the presence of a negative cycle in the graph.
   

Applications and Utility:

• The Floyd Warshall Algorithm is not just for finding the shortest paths but also for detecting negative cycles within the graph.
• It is widely used in network routing protocols, for path planning in robotics, in geographical mapping systems to find the shortest route, and in various applications where the shortest or most efficient path between points needs to be calculated.

Example

Let us understand this problem with the help of a graph. Consider the graph given below. It consists of four vertices (named as 1, 2, 3, 4 inside circles) and there are 5 directed edges with their edge weights as shown in the graph.

Intuitively, we can tell the shortest path from each vertex to every other vertex in this graph.

All pair shortest paths

Node 1:

Node 2:

Node 3:

Node 4:

As you can see in the images above, we have presented the shortest path from each node to every other node i.e. for each node pair. That’s why it is called all pair shortest paths.

Requirement of All Pair Shortest Path

There are various scenarios where we can apply the All Pair Shortest Path approach to reach the solution. Let us see some of them:

1. This algorithm is used in finding the transitive closure of directed graphs. You can go through Transitive closure of a Graph article to understand how the Floyd Warshall Algorithm (we will discuss this shortly) is used to compute the transitive closure of a directed graph.
    
2. Inversion of real matrices
    
3. To check if a given graph is bipartite or not. You can check out this problem statement from Coding Ninjas Studio to gather more knowledge around this problem.
    
4. Faster computation of PathFinder Networks

Apart from these scenarios there are numerous coding problems which can be solved using the application of any All Pair Shortest Path algorithm. These coding techniques can either involve the idea of All Pair Shortest Path as the central idea with minor modifications or this All Pair Shortest Path concept may be one of its components to get to the final solution.

Algorithms to Find All Pair Shortest Path

There are mainly two algorithms to compute all pair shortest paths in a given graph. We have elaborate articles explaining each of these algorithms. These are:

Floyd-Warshall Algorithm

Floyd-Warshall Algorithm is a dynamic programming algorithm which is used to compute the all pair shortest paths in a directed or undirected graph. The time and space complexities of this algorithm are O(V^3) and O(V^2) respectively where V is the number of vertices in the graph. 

Detailed explanation of this algorithm can be found in Coding Ninjas Studio article: Floyd-Warshall Algorithm

Johnson’s Algorithm

Johnson’s algorithm is a combination of two well-known algorithms for computing shortest paths in a graph for one node: Dijkstra’s algorithm and Bellman-Ford algorithm. It uses both these algorithms to arrive at the final solution. The time complexity of this algorithm is O((V^2)logV + VE) where V is the number of vertices in the graph and E represents the count of edges in the graph.

Detailed explanation of this algorithm is available in this Coding Ninjas Studio article: Johnson’s Algorithm.

Check out this problem - Count Inversions

Frequently Asked Questions

What is the difference between Dijkstra and all pair shortest path?

Dijkstra's algorithm finds the shortest path from a single source to all other vertices, while All-Pair Shortest Path algorithms, like Floyd Warshall, find shortest paths between every pair of vertices.

Is Dijkstra all pairs shortest path?

The Dijkstra algorithm is not the All Pair Shortest Path algorithm. It is used for finding the shortest path between a central given node and all other nodes in a graph containing edges with only non-negative weights. However, we can apply the Dijkstra algorithm V number of times to compute all pair shortest paths in a graph with non-negative edge weights.

What is all pair shortest path in Python?

All-pair shortest path is the problem of finding the shortest path in-between every pair of vertices in a weighted graph. Python provides efficient algorithms like Floyd-Warshall and Johnson's algorithm to solve this problem and obtain the shortest path.

What is the difference between single source and all pair shortest path?

Single-source shortest path algorithms (such as Dijkstra's algorithm) find the shortest path between one node and all other nodes, while all-pairs shortest path algorithms (such as Floyd-Warshall algorithm) find the shortest path in-between every pair of nodes in the graph.

What are the two types of shortest path algorithm?

The two types of shortest path algorithms are Dijkstra's algorithm and the Bellman-Ford algorithm. Dijkstra's algorithm finds the shortest path from a source node to all other nodes in non-negative edge-weighted graphs. Bellman-Ford handles graphs with negative edge weights, identifying the shortest path from a source to all other nodes.

Conclusion

This article discussed an overview of the All Pair Shortest Path problem. We developed an understanding of the problem using an elaborate example. We also came to know the various applications of the All Pair Shortest Path problems. There are various algorithms to compute the all pair shortest paths such as Floyd-Warshall and Johnson's algorithms.

We hope this blog has helped you enhance your knowledge and understanding of the All Pair Shortest Path problem. If you'd like to learn more, Check out the following links:

• Introduction to C Programming
• Data Structure
• Floyd-Warshall Algorithm
• Johnson’s Algorithm
• Prim’s MST for Adjacency List Representation
   

Head to the Guided Path on the Coding Ninjas Studio and upskill in Data Structures and Algorithms, Competitive Programming, System Design, and many more courses.

If you want to Practise top Coding Problems, attempt mock tests, or read interview experiences, head to Coding Ninjas Studio, our practice platform.