Workspace

Problem workspace

3 day streakD

Floyd–Warshall Algorithm

MediumGraphsShortest paths

The challenge

Compute shortest distances between every ordered pair of vertices. Identify whether the graph contains any negative cycle.

Directed graph; negative edges are allowed. Affected pairs have no finite minimum when they can pass through a negative cycle.

Example

On the negative-edge example, A → E improves from ∞ to 5. E → A stays ∞ because no directed return path exists.

Use the walkthrough below to inspect the input and each state change.

See Floyd–Warshall, step by step

Follow the edges. Watch the state change.

Directed · 6 vertices · 7 edgesA = 0, B = 1, …
Negative edgeDirected graph with 6 vertices. Initialize direct distances. The diagonal is zero, direct edges keep their minimum weight, and all other pairs start at infinity. Rows are sources; columns are destinations. The edge list and state table below provide the graph in text.412-2831ABCDEF
CurrentVisited / acceptedUnvisited
Distances · row → column
From / toABCDEF
A04∞∞∞1
B∞0-2∞∞∞
C∞∞03∞∞
D∞∞∞01∞
E∞∞∞∞0∞
F∞2∞∞80
Step 01 / 21

Initialize direct distances.

The diagonal is zero, direct edges keep their minimum weight, and all other pairs start at infinity. Rows are sources; columns are destinations.

distance[i][i] = 0; distance[u][v] = weight
View input edges

A → B (4) · A → F (1) · F → B (2) · B → C (-2) · F → E (8) · C → D (3) · D → E (1)

Put it into code

After iteration k, routes may use only the first k + 1 vertices as intermediates.

Vertices are numbered 0 to V − 1. C++ uses C++17 or later.

from math import inf

def floyd_warshall(n, edges):
    # Directed edges: (u, v, weight).
    distance = [[inf] * n for _ in range(n)]
    for u in range(n):
        distance[u][u] = 0
    for u, v, weight in edges:
        distance[u][v] = min(distance[u][v], weight)

    for k in range(n):  # Intermediate vertex MUST be outermost.
        for i in range(n):
            for j in range(n):
                if distance[i][k] != inf and distance[k][j] != inf:
                    distance[i][j] = min(
                        distance[i][j], distance[i][k] + distance[k][j])

    negative_cycle = any(distance[u][u] < 0 for u in range(n))
    return distance, negative_cycle  # Affected pairs have no finite minimum.

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap