# Floyd-Warshall algorithm

Hello, guys! It’s me! Warotan!

Japanese version.

The Floyd-Warshall algorithm is a way to find the minimum distance between all vertex pairs in a given graph.

I hope it will be helpful to my future self and to the lucky (?) readers who happened to come across this blog.

Also, I wrote other articles related to competitive programming.
The English version is coming soon. Please wait for it !!

## Floyd-Warshall algorithm

The Floyd-Warshall algorithm is a way to find the minimum distance between all vertex pairs in a given graph.

We consider a shortest path problem here.

Costs $$c_{ij}$$ are defined on each arrow.

In Floyd-Warshall algorithm, we can obtain the minimum distance between each vertex pair by searching all the starting, relay, and ending points.
For example, to find the minimum distance from A to C, letting the starting point be A and the ending point be C, there are 3 ways to reach C,
A -> D -> C
A -> B -> C
A -> D -> B -> C

We can take B or D as a relay point, and if B is taken, there is also a way to relay D.
If we know the best way from A to B, we can find the best way to C from B.
Therefore, when we would like to go from A to C, you can see the structure that if the whole path is optimal, then the middle part of it is also optimal.
As we say, Floyd-Warshall algorithm is a way to find the minimum distance between all pairs like Dynamic Programming.

## Implementation example

Floyd-Warshall algorithm is very simple to implement.
The computational complexity is $$O\left(\left| V\right|^3\right)$$ as we search all starting, relay, and ending points, $$\left| V\right|$$ is the number of vertices.

vector<vector<int>> Warshall_Floyd(int v, vector<vector<int>> graph){
vector<vector<int>> cost = graph;
for(int k = 0;k < v;k++){
for(int i = 0;i < v;i++){
for(int j = 0;j < v;j++){
cost[i][j] = min(cost[i][j],cost[i][k]+cost[k][j]);
}
}
}
}

return cost;
}

This function returns the minimum cost cost[i][j] for each pair $$\left(i,j\right)$$ by taking the number of vertices $$v$$ and a weighted directed graph graph.
Here, we consider the cost of unconnected sides is defined as $$\infty$$ and graph[i][i] = 0.
The index k represents the relay point and i,j the starting and ending point.

## Summary

Now, that’s all what I wanted to write.

This time, I introduced Floyd-Warshall algorithm that finds the minimum distance between all verticex pairs with $$O\left(\left| V\right|^3\right)$$.