Write and explain the Floyd Warshall algorithm to find the all pair shortest path.

The Floyd Warshall algorithm is a dynamic programming algorithm used to find the shortest paths between all pairs of vertices in a graph. It works with both directed and undirected graphs, but it does not work with graphs that contain negative cycles.

Here are the steps of the Floyd Warshall algorithm:

1. Initialization: Create a matrix 'dist' of size VxV where V is the number of vertices in the given graph. Fill the diagonal elements of the matrix with 0s (since the distance from a vertex to itself is 0) and the rest with the weights of the edges if there is a direct edge between the vertices, or infinity if there is no direct edge.

2. For each vertex, consider it as an intermediate vertex for all pairs of vertices. Update the distance value of all pairs of vertices by comparing the existing distance value with the distance value if we go through the current intermediate vertex. If the latter is smaller, update the distance value to that.

3. Repeat step 2 for all vertices.

4. After considering all vertices as an intermediate vertex, the 'dist' matrix will have the shortest distances between all pairs of vertices.

The time complexity of the Floyd Warshall algorithm is O(V^3) as there are 3 nested loops each running V times, where V is the number of vertices in the graph.

The space complexity is O(V^2) for the distance matrix.

The Floyd Warshall algorithm is used when we want to find the shortest distances between all pairs of vertices, especially when there are negative weights and direct edges between all pairs of vertices. However, it is not suitable for graphs with negative cycles.