Shortest Path Problems in Weighted Graphs

A systematic treatment of shortest path algorithms: BFS for unweighted graphs, Dijkstra's algorithm with a correctness proof, the Bellman--Ford algorithm with negative-cycle detection, the Floyd--Warshall algorithm, and shortest paths in DAGs.

Folio Official

March 1, 2026

1. Formulation of the Shortest Path Problem

Definition 1 (Weighted graph and path weight).

A weighted graph

G = (V, E, w)

consists of a graph

G = (V, E)

together with a weight function

w : E \to R

. The weight (or length) of a path

P = v_{0} v_{1} \dots v_{k}

w (P) = i = 0 \sum k - 1 w (v_{i}, v_{i + 1}) .

Definition 2 (Shortest path and shortest distance).

Let

P (s, t)

denote the set of all paths from

s

t

. The shortest distance is

δ (s, t) = ⎩ ⎨ ⎧ min_{P \in P (s, t)} w (P) - \infty \infty if P (s, t) \neq = \emptyset and no negative cycle is reachable, if a negative cycle is reachable from s on a path to t, if P (s, t) = \emptyset.

A path

P

with

w (P) = δ (s, t)

is called a shortest path.

Remark 3.

If a cycle of negative total weight (a negative cycle) is reachable, one can traverse it arbitrarily many times to make the path weight arbitrarily small, so no shortest path exists. We encode this situation as

δ (s, t) = - \infty

A weighted graph with edge weights. The shortest path from $s$ to $t$ is $s \to a \to b \to t$ with total weight $1 + 2 + 3 = 6$ , not the direct edge $s \to t$ of weight $10$ :

2. BFS Shortest Paths: The Unweighted Case

When every edge has weight $1$ , BFS (breadth-first search) correctly computes shortest distances.

Theorem 4 (Correctness of BFS).

In an unweighted graph

G = (V, E)

, run BFS from a source

s

and let

d [v]

be the layer at which

v

is discovered. Then

d [v] = δ (s, v)

for every

v \in V

Proof.

We proceed by induction on

k = δ (s, v)

. For

k = 0

we have

v = s

and

d [s] = 0

. Suppose

k \geq 1

and that the claim holds for all vertices at distance at most

k - 1

. Let

s = u_{0}, u_{1}, \dots, u_{k} = v

be a shortest path. By induction,

d [u_{k - 1}] = k - 1

. When BFS processes

u_{k - 1}

, it enqueues

v

(if not already visited), so

d [v] \leq k

. On the other hand,

d [v] < k

would imply

δ (s, v) < k

(since BFS traverses each edge in one step), a contradiction. Hence

d [v] = k

. □

The running time of BFS is $O (∣ V ∣ + ∣ E ∣)$ .

BFS discovers vertices layer by layer. Starting from $s$ , layer $0$ contains $s$ , layer $1$ its neighbors, layer $2$ the neighbors' neighbors, and so on:

Algorithm 1: Breadth-First Search (BFS)

Input:

Graph

G = (V, E)

, source

s

Output:

Shortest distances

d [v]

for all

v \in V

d [v] \leftarrow + \infty

end for

d [s] \leftarrow 0

Queue

Q \leftarrow \emptyset

Enqueue(

Q, s

)

while

Q \neq = \emptyset

u \leftarrow Dequeue (Q)

for all

v \in Adj (u)

d [v] = + \infty

d [v] \leftarrow d [u] + 1

Enqueue(

Q, v

)

end if

end for

end while

return

d

3. Dijkstra's Algorithm

Consider the following graph with nonnegative weights. Starting from $s$ , Dijkstra's algorithm finalizes vertices in order of increasing distance: $s$ ( $d = 0$ ), $a$ ( $d = 1$ ), $b$ ( $d = 3$ ), $c$ ( $d = 4$ ), $t$ ( $d = 6$ ):

When all edge weights are nonnegative, Dijkstra's algorithm efficiently solves the single-source shortest path problem. The algorithm maintains a set $S$ of vertices whose shortest distances have been finalized. At each step, it selects the vertex $u \in / S$ with the smallest tentative distance $d [u]$ , adds $u$ to $S$ , and relaxes the edges leaving $u$ .

Definition 5 (Relaxation).

Relaxation of an edge

(u, v)

is the operation: if

d [v] > d [u] + w (u, v)

, update

d [v] \leftarrow d [u] + w (u, v)

Theorem 6 (Correctness of Dijkstra's algorithm).

When all edge weights are nonnegative, Dijkstra's algorithm correctly computes

d [v] = δ (s, v)

for every vertex

v

Proof.

We show by induction on the order in which vertices are added to

S

that

d [u] = δ (s, u)

at the moment

u

is added.

Base case. The source

s

is added first with

d [s] = 0 = δ (s, s)

Inductive step. Let

u

be the next vertex added to

S

, and suppose for contradiction that

d [u] > δ (s, u)

. Consider a shortest path

P

from

s

u

. Let

(x, y)

be the first edge on

P

with

x \in S

and

y \in / S

. By induction,

d [x] = δ (s, x)

. When

x

was added to

S

, the edge

(x, y)

was relaxed, so

d [y] \leq d [x] + w (x, y) = δ (s, x) + w (x, y) = δ (s, y) .

Since

w \geq 0

and

y

precedes

u

P

, we have

δ (s, y) \leq δ (s, u)

. Thus

d [y] \leq δ (s, u) < d [u]

. But

u

was chosen as the vertex outside

S

with the smallest

d

-value, so

d [u] \leq d [y]

— a contradiction. □

Algorithm 2: Dijkstra's Algorithm

Input:

Graph

G = (V, E)

, nonnegative weights

w

, source

s

Output:

Shortest distances

d [v]

for all

v \in V

d [v] \leftarrow + \infty

end for

d [s] \leftarrow 0

Insert all vertices into priority queue

Q

with key

d

while

Q \neq = \emptyset

u \leftarrow ExtractMin (Q)

for all

(u, v) \in E

d [u] + w (u, v) < d [v]

d [v] \leftarrow d [u] + w (u, v)

DecreaseKey(

Q, v, d [v]

)

end if

end for

end while

return

d

Remark 7.

With a binary heap, the running time is

O ((∣ V ∣ + ∣ E ∣) lo g ∣ V ∣)

. With a Fibonacci heap, it improves to

O (∣ E ∣ + ∣ V ∣ lo g ∣ V ∣)

4. The Bellman–Ford Algorithm

When edges may have negative weights, Dijkstra's algorithm fails. The Bellman–Ford algorithm handles negative weights and can also detect negative cycles. It works by relaxing all edges $∣ V ∣ - 1$ times.

Theorem 8 (Correctness of Bellman–Ford).

If no negative cycle is reachable from

s

, then after

∣ V ∣ - 1

iterations,

d [v] = δ (s, v)

for every vertex

v

Proof.

In the absence of negative cycles, every shortest path has at most

∣ V ∣ - 1

edges. Let

s = v_{0}, v_{1}, \dots, v_{k} = v

(with

k \leq ∣ V ∣ - 1

) be a shortest path from

s

v

. We claim that after iteration

i

d [v_{i}] = δ (s, v_{i})

. For

i = 0

d [s] = 0

. Assuming the claim for

i - 1

: after iteration

i - 1

d [v_{i - 1}] = δ (s, v_{i - 1})

. In iteration

i

, the edge

(v_{i - 1}, v_{i})

is relaxed, giving

d [v_{i}] \leq d [v_{i - 1}] + w (v_{i - 1}, v_{i}) = δ (s, v_{i - 1}) + w (v_{i - 1}, v_{i}) = δ (s, v_{i}) .

Since

d [v_{i}] \geq δ (s, v_{i})

always holds (relaxation never makes

d

smaller than the true distance), equality follows. □

Theorem 9 (Negative cycle detection).

After

∣ V ∣ - 1

iterations, perform one additional pass over all edges. If any

d [v]

is updated, then a negative cycle reachable from

s

exists.

Proof.

If no negative cycle exists, all

d

-values are finalized after

∣ V ∣ - 1

iterations and no update occurs in the extra pass. By contrapositive, an update implies a negative cycle. □

The running time of Bellman–Ford is $O (∣ V ∣ \cdot ∣ E ∣)$ .

Algorithm 3: Bellman–Ford Algorithm

Input:

Directed graph

G = (V, A)

, weights

w

, source

s

Output:

Shortest distances

d [v]

, negative cycle detection

for all

v \in V

d [v] \leftarrow + \infty

end for

d [s] \leftarrow 0

for

i = 1

∣ V ∣ - 1

for all

(u, v) \in A

d [u] + w (u, v) < d [v]

d [v] \leftarrow d [u] + w (u, v)

end if

end for

// Negative cycle detection

for all

(u, v) \in A

d [u] + w (u, v) < d [v]

return "Negative cycle exists"

end if

end for

return

d

5. The Floyd–Warshall Algorithm

The Floyd–Warshall algorithm computes shortest distances between all pairs of vertices using dynamic programming.

Theorem 10 (Floyd–Warshall recurrence).

Let

V = {1, 2, \dots, n}

, and let

d^{(k)} (i, j)

be the weight of a shortest path from

i

j

using only vertices in

{1, \dots, k}

as intermediaries. Then

d^{(k)} (i, j) = min (d^{(k - 1)} (i, j), d^{(k - 1)} (i, k) + d^{(k - 1)} (k, j)),

and

d^{(n)} (i, j) = δ (i, j)

Proof.

A shortest path from

i

j

that avoids vertex

k

as an intermediate has weight

d^{(k - 1)} (i, j)

. A shortest path that does pass through

k

decomposes as

i \to \dots \to k \to \dots \to j

; in the absence of negative cycles,

k

appears at most once, so its weight is

d^{(k - 1)} (i, k) + d^{(k - 1)} (k, j)

. The minimum of these two cases gives

d^{(k)} (i, j)

. □

Algorithm 4: Floyd–Warshall Algorithm

Input:

Directed graph

G = (V, A)

, weights

w

V = {1, \dots, n}

Output:

All-pairs shortest distances

d [i] [j]

for

i = 1

n

for

j = 1

n

i = j

d [i] [j] \leftarrow 0

else if

(i, j) \in A

d [i] [j] \leftarrow w (i, j)

else

d [i] [j] \leftarrow + \infty

end if

end for

for

k = 1

n

for

i = 1

n

for

j = 1

n

d [i] [j] \leftarrow min (d [i] [j], d [i] [k] + d [k] [j])

end for

return

d

The running time is $O (∣ V ∣^{3})$ . A negative cycle through vertex $i$ is detected when $d^{(n)} (i, i) < 0$ .

6. Shortest Paths in DAGs

Theorem 11 (Linear-time shortest paths in DAGs).

In a DAG (directed acyclic graph), single-source shortest paths can be computed in

O (∣ V ∣ + ∣ E ∣)

time by processing vertices in topological order and relaxing each edge exactly once.

Proof.

In a topological ordering, whenever an edge

(u, v)

exists,

u

appears before

v

. Therefore, by the time vertex

v

is processed, every edge

(u, v)

entering

v

has already been relaxed with the correct value

d [u] = δ (s, u)

. The relaxation of

(u, v)

then yields

d [v] = δ (s, v)

. □

Remark 12.

This method works correctly even with negative edge weights, since a DAG has no cycles and hence no negative cycles. It is widely applied in project scheduling: computing the longest path (critical path) in a DAG is the basis of PERT (Program Evaluation and Review Technique).

Graph Theory Discrete Mathematics Textbook Shortest Paths Dijkstra Bellman-Ford

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Shortest Path Problems in Weighted Graphs

Folio Official

March 1, 2026

1. Formulation of the Shortest Path Problem

Definition 1 (Weighted graph and path weight).

A weighted graph

G = (V, E, w)

consists of a graph

G = (V, E)

together with a weight function

w : E \to R

. The weight (or length) of a path

P = v_{0} v_{1} \dots v_{k}

w (P) = i = 0 \sum k - 1 w (v_{i}, v_{i + 1}) .

Definition 2 (Shortest path and shortest distance).

Let

P (s, t)

denote the set of all paths from

s

t

. The shortest distance is

δ (s, t) = ⎩ ⎨ ⎧ min_{P \in P (s, t)} w (P) - \infty \infty if P (s, t) \neq = \emptyset and no negative cycle is reachable, if a negative cycle is reachable from s on a path to t, if P (s, t) = \emptyset.

A path

P

with

w (P) = δ (s, t)

is called a shortest path.

Remark 3.

δ (s, t) = - \infty

A weighted graph with edge weights. The shortest path from $s$ to $t$ is $s \to a \to b \to t$ with total weight $1 + 2 + 3 = 6$ , not the direct edge $s \to t$ of weight $10$ :

2. BFS Shortest Paths: The Unweighted Case

When every edge has weight $1$ , BFS (breadth-first search) correctly computes shortest distances.

Theorem 4 (Correctness of BFS).

In an unweighted graph

G = (V, E)

, run BFS from a source

s

and let

d [v]

be the layer at which

v

is discovered. Then

d [v] = δ (s, v)

for every

v \in V

Proof.

We proceed by induction on

k = δ (s, v)

. For

k = 0

we have

v = s

and

d [s] = 0

. Suppose

k \geq 1

and that the claim holds for all vertices at distance at most

k - 1

. Let

s = u_{0}, u_{1}, \dots, u_{k} = v

be a shortest path. By induction,

d [u_{k - 1}] = k - 1

. When BFS processes

u_{k - 1}

, it enqueues

v

(if not already visited), so

d [v] \leq k

. On the other hand,

d [v] < k

would imply

δ (s, v) < k

(since BFS traverses each edge in one step), a contradiction. Hence

d [v] = k

. □

The running time of BFS is $O (∣ V ∣ + ∣ E ∣)$ .

BFS discovers vertices layer by layer. Starting from $s$ , layer $0$ contains $s$ , layer $1$ its neighbors, layer $2$ the neighbors' neighbors, and so on:

Algorithm 1: Breadth-First Search (BFS)

Input:

Graph

G = (V, E)

, source

s

Output:

Shortest distances

d [v]

for all

v \in V

d [v] \leftarrow + \infty

end for

d [s] \leftarrow 0

Queue

Q \leftarrow \emptyset

Enqueue(

Q, s

)

while

Q \neq = \emptyset

u \leftarrow Dequeue (Q)

for all

v \in Adj (u)

d [v] = + \infty

d [v] \leftarrow d [u] + 1

Enqueue(

Q, v

)

end if

end for

end while

return

d

3. Dijkstra's Algorithm

Definition 5 (Relaxation).

Relaxation of an edge

(u, v)

is the operation: if

d [v] > d [u] + w (u, v)

, update

d [v] \leftarrow d [u] + w (u, v)

Theorem 6 (Correctness of Dijkstra's algorithm).

When all edge weights are nonnegative, Dijkstra's algorithm correctly computes

d [v] = δ (s, v)

for every vertex

v

Proof.

We show by induction on the order in which vertices are added to

S

that

d [u] = δ (s, u)

at the moment

u

is added.

Base case. The source

s

is added first with

d [s] = 0 = δ (s, s)

Inductive step. Let

u

be the next vertex added to

S

, and suppose for contradiction that

d [u] > δ (s, u)

. Consider a shortest path

P

from

s

u

. Let

(x, y)

be the first edge on

P

with

x \in S

and

y \in / S

. By induction,

d [x] = δ (s, x)

. When

x

was added to

S

, the edge

(x, y)

was relaxed, so

d [y] \leq d [x] + w (x, y) = δ (s, x) + w (x, y) = δ (s, y) .

Since

w \geq 0

and

y

precedes

u

P

, we have

δ (s, y) \leq δ (s, u)

. Thus

d [y] \leq δ (s, u) < d [u]

. But

u

was chosen as the vertex outside

S

with the smallest

d

-value, so

d [u] \leq d [y]

— a contradiction. □

Algorithm 2: Dijkstra's Algorithm

Input:

Graph

G = (V, E)

, nonnegative weights

w

, source

s

Output:

Shortest distances

d [v]

for all

v \in V

d [v] \leftarrow + \infty

end for

d [s] \leftarrow 0

Insert all vertices into priority queue

Q

with key

d

while

Q \neq = \emptyset

u \leftarrow ExtractMin (Q)

for all

(u, v) \in E

d [u] + w (u, v) < d [v]

d [v] \leftarrow d [u] + w (u, v)

DecreaseKey(

Q, v, d [v]

)

end if

end for

end while

return

d

Remark 7.

With a binary heap, the running time is

O ((∣ V ∣ + ∣ E ∣) lo g ∣ V ∣)

. With a Fibonacci heap, it improves to

O (∣ E ∣ + ∣ V ∣ lo g ∣ V ∣)

4. The Bellman–Ford Algorithm

Theorem 8 (Correctness of Bellman–Ford).

If no negative cycle is reachable from

s

, then after

∣ V ∣ - 1

iterations,

d [v] = δ (s, v)

for every vertex

v

Proof.

In the absence of negative cycles, every shortest path has at most

∣ V ∣ - 1

edges. Let

s = v_{0}, v_{1}, \dots, v_{k} = v

(with

k \leq ∣ V ∣ - 1

) be a shortest path from

s

v

. We claim that after iteration

i

d [v_{i}] = δ (s, v_{i})

. For

i = 0

d [s] = 0

. Assuming the claim for

i - 1

: after iteration

i - 1

d [v_{i - 1}] = δ (s, v_{i - 1})

. In iteration

i

, the edge

(v_{i - 1}, v_{i})

is relaxed, giving

d [v_{i}] \leq d [v_{i - 1}] + w (v_{i - 1}, v_{i}) = δ (s, v_{i - 1}) + w (v_{i - 1}, v_{i}) = δ (s, v_{i}) .

Since

d [v_{i}] \geq δ (s, v_{i})

always holds (relaxation never makes

d

smaller than the true distance), equality follows. □

Theorem 9 (Negative cycle detection).

After

∣ V ∣ - 1

iterations, perform one additional pass over all edges. If any

d [v]

is updated, then a negative cycle reachable from

s

exists.

Proof.

If no negative cycle exists, all

d

-values are finalized after

∣ V ∣ - 1

iterations and no update occurs in the extra pass. By contrapositive, an update implies a negative cycle. □

The running time of Bellman–Ford is $O (∣ V ∣ \cdot ∣ E ∣)$ .

Algorithm 3: Bellman–Ford Algorithm

Input:

Directed graph

G = (V, A)

, weights

w

, source

s

Output:

Shortest distances

d [v]

, negative cycle detection

for all

v \in V

d [v] \leftarrow + \infty

end for

d [s] \leftarrow 0

for

i = 1

∣ V ∣ - 1

for all

(u, v) \in A

d [u] + w (u, v) < d [v]

d [v] \leftarrow d [u] + w (u, v)

end if

end for

// Negative cycle detection

for all

(u, v) \in A

d [u] + w (u, v) < d [v]

return "Negative cycle exists"

end if

end for

return

d

5. The Floyd–Warshall Algorithm

The Floyd–Warshall algorithm computes shortest distances between all pairs of vertices using dynamic programming.

Theorem 10 (Floyd–Warshall recurrence).

Let

V = {1, 2, \dots, n}

, and let

d^{(k)} (i, j)

be the weight of a shortest path from

i

j

using only vertices in

{1, \dots, k}

as intermediaries. Then

d^{(k)} (i, j) = min (d^{(k - 1)} (i, j), d^{(k - 1)} (i, k) + d^{(k - 1)} (k, j)),

and

d^{(n)} (i, j) = δ (i, j)

Proof.

A shortest path from

i

j

that avoids vertex

k

as an intermediate has weight

d^{(k - 1)} (i, j)

. A shortest path that does pass through

k

decomposes as

i \to \dots \to k \to \dots \to j

; in the absence of negative cycles,

k

appears at most once, so its weight is

d^{(k - 1)} (i, k) + d^{(k - 1)} (k, j)

. The minimum of these two cases gives

d^{(k)} (i, j)

. □

Algorithm 4: Floyd–Warshall Algorithm

Input:

Directed graph

G = (V, A)

, weights

w

V = {1, \dots, n}

Output:

All-pairs shortest distances

d [i] [j]

for

i = 1

n

for

j = 1

n

i = j

d [i] [j] \leftarrow 0

else if

(i, j) \in A

d [i] [j] \leftarrow w (i, j)

else

d [i] [j] \leftarrow + \infty

end if

end for

for

k = 1

n

for

i = 1

n

for

j = 1

n

d [i] [j] \leftarrow min (d [i] [j], d [i] [k] + d [k] [j])

end for

return

d

The running time is $O (∣ V ∣^{3})$ . A negative cycle through vertex $i$ is detected when $d^{(n)} (i, i) < 0$ .

6. Shortest Paths in DAGs

Theorem 11 (Linear-time shortest paths in DAGs).

In a DAG (directed acyclic graph), single-source shortest paths can be computed in

O (∣ V ∣ + ∣ E ∣)

time by processing vertices in topological order and relaxing each edge exactly once.

Proof.

In a topological ordering, whenever an edge

(u, v)

exists,

u

appears before

v

. Therefore, by the time vertex

v

is processed, every edge

(u, v)

entering

v

has already been relaxed with the correct value

d [u] = δ (s, u)

. The relaxation of

(u, v)

then yields

d [v] = δ (s, v)

. □

Remark 12.

Graph Theory Discrete Mathematics Textbook Shortest Paths Dijkstra Bellman-Ford

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Shortest Path Problems in Weighted Graphs

1. Formulation of the Shortest Path Problem

2. BFS Shortest Paths: The Unweighted Case

3. Dijkstra's Algorithm

4. The Bellman–Ford Algorithm

5. The Floyd–Warshall Algorithm

6. Shortest Paths in DAGs

Share your expertise with the world

More from Folio Official

Paths and Connectivity

Eulerian and Hamiltonian Graphs: Two Classical Traversal Problems

Network Flows

Recurrence Relations and Counting: Solving Linear Recurrences

Shortest Path Problems in Weighted Graphs

1. Formulation of the Shortest Path Problem

2. BFS Shortest Paths: The Unweighted Case

3. Dijkstra's Algorithm

4. The Bellman–Ford Algorithm

5. The Floyd–Warshall Algorithm

6. Shortest Paths in DAGs

Share your expertise with the world

More from Folio Official

Paths and Connectivity

Eulerian and Hamiltonian Graphs: Two Classical Traversal Problems

Network Flows

Recurrence Relations and Counting: Solving Linear Recurrences