Floyd Algorithm

01 Dec 2024

1. Introduction

The Floyd algorithm finds the shortest distance between every pair of vertices in a graph, so it is also called an all-pairs shortest-path algorithm. It is useful when a graph has relatively few vertices but requires shortest-distance queries for many pairs of vertices.

The algorithm uses a two-dimensional array dist, where dist[i][j] is the current shortest distance from i to j. Because it stores distances for every pair, its space complexity is O(n²). Its three nested loops take O(n³) time, so it is usually used for graphs with at most a few hundred vertices.

2. Core Idea

Initially, dist[i][j] stores only the weight of a direct edge from i to j. If there is no direct edge, the distance is set to a sufficiently large value. The distance from every vertex to itself is 0.

Then, vertices 1 through n are considered as possible intermediate vertices in order. When vertex k is allowed as an intermediate vertex, there are two possible routes from i to j:

Do not pass through k, keeping the distance dist[i][j].
Pass through k, giving the distance dist[i][k] + dist[k][j].

Take the smaller of the two values to update dist[i][j]:

for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

The intermediate vertex k must be the outermost loop. After round k finishes, every shortest path is allowed to use only vertices 1 through k as intermediate vertices, which makes the dynamic-programming state complete.

3. Example: Multiple Shortest-Path Queries

Given an undirected weighted graph, read its roads and answer multiple queries asking for the shortest distance from x to y. Run Floyd once, then answer every query directly with dist[x][y].

#include <bits/stdc++.h>
using namespace std;

const long long INF = (long long)4e18;
long long dist[510][510];
int n, m;

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dist[i][j] = (i == j ? 0 : INF);
        }
    }

    while (m--) {
        int x, y;
        long long w;
        cin >> x >> y >> w;
        dist[x][y] = min(dist[x][y], w);
        dist[y][x] = min(dist[y][x], w);
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;

        if (dist[x][y] == INF) cout << -1 << '\n';
        else cout << dist[x][y] << '\n';
    }
    return 0;
}

For example, suppose the roads are 1 - 2 with weight 2, 2 - 3 with weight 3, 1 - 3 with weight 10, and 3 - 4 with weight 1. The shortest distance from 1 to 4 is 6, along the route 1 → 2 → 3 → 4.

Floyd is suitable for small graphs where any pair of vertices may be queried. If the graph is large, only distances from one start vertex are needed, and all edge weights are non-negative, Dijkstra’s algorithm is usually a better choice. Floyd also requires that the graph have no reachable negative cycle; otherwise, a shortest distance has no finite value.

Floyd Algorithm

Related Posts