Floyd–Warshall

Compute shortest distances between every pair of vertices. It is a useful choice for small dense graphs.

Prerequisites: Basic C++ input/output, vectors, loops, and the preceding graph lessons.

Build the idea

1. Initialize diagonal distances to 0 and edges to their minimum weight.
2. For each intermediate vertex k, consider going i→k→j.
3. The outer k loop progressively permits more intermediate vertices.
4. A negative diagonal after completion indicates a negative cycle.
5. distance[from][to] is the best route using already permitted intermediate vertices. The loop over the intermediate vertex middle must be outermost. Guard INF before adding; retain zero diagonals and minimum parallel weights. This program rejects any negative cycle rather than printing misleading finite distances.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    const long long INF=(1LL<<60);
    vector<vector<long long>>distance(n+1,vector<long long>(n+1,INF));
    for(int vertex=1;vertex<=n;vertex++){
        distance[vertex][vertex]=0;
    }
    for(int i=0;i<m;i++){
        int from,to;
        long long weight;
        cin>>from>>to>>weight;
        distance[from][to]=min(distance[from][to],weight); // Keep the cheapest parallel edge.
    }
    for(int vertex=1;vertex<=n;vertex++){
        if(distance[vertex][vertex]<0){
            cout<<"NEGATIVE CYCLE\n";
            return 0;
        }
    }
    for(int middle=1;middle<=n;middle++){
        for(int from=1;from<=n;from++){
            for(int to=1;to<=n;to++){
                if(distance[from][middle]==INF||distance[middle][to]==INF){
                    continue;
                }
                distance[from][to]=min(distance[from][to],distance[from][middle]+distance[middle][to]);
                // Stop when a negative cycle is first certified; its repeated walks have no finite minimum.
                if(from==to&&distance[from][to]<0){
                    cout<<"NEGATIVE CYCLE\n";
                    return 0;
                }
            }
        }
    }
    for(int from=1;from<=n;from++){
        for(int to=1;to<=n;to++){
            if(to>1){
                cout<<' ';
            }
            if(distance[from][to]==INF){
                cout<<"INF";
            }
            else{
                cout<<distance[from][to];
            }
        }
        cout<<'\n';
    }
}

Complexity analysis

O(V³) time, O(V²) space.

Example input and output

Read n m and m directed weighted edges from to weight. Require 1≤n≤300 and |weight|≤10^6. Print NEGATIVE CYCLE if any exists; otherwise print the n×n distance matrix, using INF for unreachable pairs.

Input

3 3
1 2 4
2 3 -1
1 3 10

Output

0 4 3
INF 0 -1
INF INF 0

Allowing vertex 2 as an intermediate improves distance 1→3 from 10 to 4+(−1)=3. There is no route back to 1 from 2 or 3.

Practical applications

Use all-pairs shortest paths for small graphs and many source-target queries. Repeated Dijkstra is often preferable for sparse nonnegative graphs.

Check your understanding

Which loop must be outermost?

Put it into practice

Answer many shortest-route queries on a graph with at most 400 vertices.