Floyd

What is Floyd?

Floyd is an all-pairs shortest path algorithm. The difference between it and the single source shortest path algorithm is that it can find the shortest distance between all pairs of nodes in a single run, without requiring multiple calls to a single-source shortest path algorithm.

How does it works?

For all nodes, we suppose that the path of every pair of nodes is $dist[i][j]$, and we allow that there exist a k satisfying $dist[i][j] < dist[i][k] + dist[k][j]$. We traverse all nodes to find the k. So it also fits the graph with egative Edge Weights but still can not solve the Negative Weight Cycles.

vector<vector<int>> dist;
void init(int dots)
{
    dist = vector<vector<int>>(1000, INT_MAX);
    for(int i = 0; i < dots; ++i) dist[i][i] = 0;
}
void floyd(int dots)
{
    for(int k = 0; k < dots; ++k)
    {
        for(int i = 0; i < dots; ++i)
        {
            for(int j = 0; j < dots; ++)
            {
                if(dist[i][j] > dist[i][k] + dist[k][j]) dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
}

Time Complexity