Floyd-Warshall — all-pairs shortest paths, O(V³): Foundations

This page assumes you have seen nothing. Before you can read the parent note Floyd-Warshall, you must own every symbol it throws at you. We will build each one from a picture. Nothing is used before it is defined.

1. What is a graph? ( $G$ , $V$ , $E$ )

Forget equations. Draw dots and arrows.

Figure — Floyd-Warshall — all-pairs shortest paths, O(V³)

Each symbol is just shorthand for a part of the picture:

Symbol	Plain words	In the picture
$G$	the whole map	dots + arrows together
$V$	all the dots	the circles labelled $0, 1, 2$
$E$	all the connectors	the arrows

2. Directed vs undirected, and weights ( $w (i, j)$ )

Two extra facts live on each road.

So $w (0, 1) = 4$ means: the one-way road from city $0$ to city $1$ costs $4$ .

3. A path, its length, and "shortest"

In the figure the direct road $0 \to 2$ costs $11$ , but the detour $0 \to 1 \to 2$ costs $4 + 2 = 6$ . So $d (0, 2) = 6$ , not $11$ . A detour can beat the direct road — that single fact is the engine of the whole algorithm.

4. The distance matrix ( $d$ , and the $\infty$ symbol)

We store all those $V \times V$ answers in a grid called a matrix.

Why $0$ on the diagonal? The distance from a city to itself is zero — you are already there.

5. The two tools: `min` and adding two half-paths

Everything Floyd-Warshall computes is built from just these two moves.

Put the two tools together and you get the heart of the parent note: $d [i] [j] \leftarrow min (d [i] [j], d [i] [k] + d [k] [j])$ In words: "Is stopping at $k$ cheaper than my current best? If so, adopt it."

6. The intermediate vertex $k$ and the notation ${1, \dots, k}$

The trickiest symbol in the parent note is the subscript in $d_{k} (i, j)$ .

7. Negative edges and negative cycles

Prerequisite map

Everything on the left feeds the single relaxation step $H$ , which repeated over growing allowed sets $J$ is the algorithm $K$ .

Equipment checklist

Read each line, answer in your head, then reveal:

What do

V

and

E

stand for in

G = (V, E)

V

= the set of vertices (dots / cities);

E

= the set of edges (arrows / roads).

What does a directed edge

i \to j

allow, and not allow?

Travel from

i

j

only; it does not grant travel from

j

i

What is

w (i, j)

The cost (weight) written on the road from

i

j

What is the length of the path

0 \to 1 \to 2

w (0, 1) + w (1, 2)

— the sum of the weights of the roads used.

What does

d (i, j)

mean?

The length of the shortest path from

i

j

Why do we initialise unknown distances to

\infty

So any real path is smaller and will replace it;

\infty

means "no known road yet."

Why is

d [i] [i]

set to

0

at the start?

The distance from a city to itself is zero — you are already there.

What does

min (a, b)

do and why is it the right tool?

Returns the smaller value; "best route" means cheapest, so we keep the smaller cost.

When you split a path through

k

, what is its cost?

d (i, k) + d (k, j)

— cost to reach

k

plus cost onward from

k

Read

d_{k} (i, j)

aloud in plain words.

Shortest distance from

i

j

using only cities

1

through

k

as intermediate stops.

What is the difference between a negative edge and a negative cycle?

A negative edge is a single cost-reducing road (allowed); a negative cycle is a loop whose weights sum below zero (forbidden — makes shortest path undefined).

How would you spot a negative cycle after running the algorithm?

Some diagonal entry

d [i] [i]

becomes less than

0

Now you own every symbol. Return to the parent note and the recurrence will read like plain English.