1 of 11

The Bellman-Ford Shortest Path Algorithm ��

2 of 11

Class Overview

  • The shortest path problem

​

  • Differences

​

  • The Bellman-Ford algorithm

​

  • Time complexity

3 of 11

Shortest Path Problem

  • Weighted path length (cost): The sum of the weights of all links on the path.

​

  • The single-source shortest path problem: Given a weighted graph G and a source vertex s, find the shortest (minimum cost) path from s to every other vertex in G.

​

​

4 of 11

Differences

  • Negative link weight: The Bellman-Ford algorithm works; Dijkstra’s algorithm doesn’t.

​

  • Distributed implementation: The Bellman-Ford algorithm can be easily implemented in a distributed way. Dijkstra’s algorithm cannot.

​

  • Time complexity: The Bellman-Ford algorithm is higher than Dijkstra’s algorithm.

​

​

5 of 11

The Bellman-Ford Algorithm

∞,nil

∞,nil

∞,nil

0

6

7

9

5

-3

8

7

-4

2

∞,nil

s

y

z

x

t

-2

6 of 11

The Bellman-Ford Algorithm

∞,nil

∞,nil

∞,nil

0

6

7

9

5

-3

8

7

-4

2

∞,nil

s

y

z

x

t

-2

6,s

7,s

∞,nil

0

6

7

9

5

-3

8

7

-4

2

∞,nil

s

y

z

x

t

-2

Initialization

After pass 1

6,s

7,s

4,y

0

6

7

9

5

-3

8

7

-4

2

2,t

s

y

z

x

t

-2

After pass 2

2,x

7,s

4,y

0

6

7

9

5

-3

8

7

-4

2

2,t

s

y

z

x

t

-2

After pass 3

The order of edges examined in each pass:�(t, x), (t, z), (x, t), (y, x), (y, t), (y, z), (z, x), (z, s), (s, t), (s, y)

7 of 11

The Bellman-Ford Algorithm

After pass 4

2,x

7,s

4,y

0

6

7

9

5

-3

8

7

-4

2

-2,t

s

y

z

x

t

-2

The order of edges examined in each pass:�(t, x), (t, z), (x, t), (y, x), (y, t), (y, z), (z, x), (z, s), (s, t), (s, y)

8 of 11

Bellman-Ford algorithm

8

9 of 11

The Bellman-Ford Algorithm

Bellman-Ford(G, w, s)

  1. Initialize-Single-Source(G, s)
  2. for i := 1 to |V| - 1 do
  3. for each edge (u, v) ∈ E do
  4. Relax(u, v, w)
  5. for each vertex v ∈ u.adj do
  6. if d[v] > d[u] + w(u, v)
  7. then return False // there is a negative cycle
  8. return True

Relax(u, v, w)

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

then d[v] := d[u] + w(u, v)

parent[v] := u

10 of 11

So if Bellman-Ford has not converged after V(G) - 1 iterations, then there cannot be a shortest path tree, so there must be a negative weight cycle.

11 of 11

Time Complexity

Bellman-Ford(G, w, s)

  1. Initialize-Single-Source(G, s)
  2. for i := 1 to |V| - 1 do
  3. for each edge (u, v) ∈ E do
  4. Relax(u, v, w)
  5. for each vertex v ∈ u.adj do
  6. if d[v] > d[u] + w(u, v)
  7. then return False // there is a negative cycle
  8. return True

O(|V|)

O(|V||E|)

O(|E|)

Time complexity: O(|V||E|)