Algorithms R OBERT S EDGEWICK | K EVIN W AYNE

S HORTEST P ATHS

Modi ed by: Dr. Fahed Jubair

Computer Engineering Department
Algorithms F O U R T H E D I T I O N
University of Jordan

R OBERT S EDGEWICK | K EVIN W AYNE

http://algs4.cs.princeton.edu
fi
Shortest paths in an edge-weighted digraph

Given an edge-weighted digraph, nd the shortest path from s to t.

edge-weighted digraph
4->5 0.35
5->4 0.35
4->7 0.37
5->7 0.28
7->5 0.28
5->1 0.32
0->4 0.38
0->2 0.26
7->3 0.39 shortest path from 0 to 6
1->3 0.29
0->2 0.26
2->7 0.34
2->7 0.34
6->2 0.40
7->3 0.39
3->6 0.52
3->6 0.52
6->0 0.58
6->4 0.93

An edge-weighted digraph and a shortest path

2
fi
Google maps

3
Shortest path applications

PERT/CPM.
Map routing.
Seam carving.
Texture mapping.
Robot navigation.
Typesetting in TeX. http://en.wikipedia.org/wiki/Seam_carving

Urban traf c planning.

Optimal pipelining of VLSI chip.
Telemarketer operator scheduling.
Routing of telecommunications messages.
Network routing protocols (OSPF, BGP, RIP).
Exploiting arbitrage opportunities in currency exchange.
Optimal truck routing through given traf c congestion pattern.

Reference: Network Flows: Theory, Algorithms, and Applications, R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Prentice Hall, 1993.

4
fi
fi
Shortest path variants

Which vertices?
Single source: from one vertex s to every other vertex.
Single sink: from every vertex to one vertex t.
Source-sink: from one vertex s to another t.
All pairs: between all pairs of vertices.

Restrictions on edge weights?

Nonnegative weights.
Arbitrary weights.

Cycles?
No directed cycles.
No "negative cycles."
which variant?

Simplifying assumption. Shortest paths from s to each vertex v exist.

5
 S HORTEST P ATHS
‣ APIs
‣ Dijkstra's algorithm
‣ Bellman-Ford algorithm
Algorithms
R OBERT S EDGEWICK | K EVIN W AYNE

http://algs4.cs.princeton.edu
Weighted directed edge API

public class DirectedEdge

DirectedEdge(int v, int w, double weight) weighted edge v→w

int from() vertex v

int to() vertex w

double weight() weight of this edge

String toString() string representation

weight
v w

Idiom for processing an edge e: int v = e.from(), w = e.to();

7
 Weighted directed edge: implementation in Java

public class DirectedEdge

{
private nal int v, w;
private nal double weight;

public DirectedEdge(int v, int w, double weight)

{
this.v = v;
this.w = w;
this.weight = weight;
} from() and to() replace
either() and other()
public int from()
{ return v; }

public int to()

{ return w; }

public int weight() 8

fi
fi
Edge-weighted digraph API

public class EdgeWeightedDigraph

EdgeWeightedDigraph(int V) edge-weighted digraph with V vertices

EdgeWeightedDigraph(In in) edge-weighted digraph from input stream

void addEdge(DirectedEdge e) add weighted directed edge e

Iterable<DirectedEdge> adj(int v) edges pointing from v

int V() number of vertices

int E() number of edges

Iterable<DirectedEdge> edges() all edges

String toString() string representation

Conventions. Allow self-loops and parallel edges.

9
Edge-weighted digraph: adjacency-lists representation

tinyEWD.txt
V 0 2 .26 0 4 .38
8 E
15
4 5 0.35 1 3 .29
adj
5 4 0.35
0
4 7 0.37 2 7 .34 Bag objects
5 7 0.28 1
7 5 0.28 2
5 1 0.32 3 6 .52 reference to a
3 DirectedEdge
0 4 0.38
0 2 0.26 4 object
4 7 .37 4 5 .35
7 3 0.39 5
1 3 0.29
6
2 7 0.34 5 1 .32 5 7 .28 5 4 .35
6 2 0.40 7
3 6 0.52
6 4 .93 6 0 .58 6 2 .40
6 0 0.58
6 4 0.93
7 3 .39 7 5 .28

Edge-weighted digraph representation

10
 Edge-weighted digraph: adjacency-lists implementation in Java

Same as EdgeWeightedGraph except replace Graph with Digraph.

public class EdgeWeightedDigraph

{
private nal int V;
private nal Bag<DirectedEdge>[] adj;

public EdgeWeightedDigraph(int V)
{
this.V = V;
adj = (Bag<DirectedEdge>[]) new Bag[V];
for (int v = 0; v < V; v++)
adj[v] = new Bag<DirectedEdge>();
}
add edge e = v→w to
public void addEdge(DirectedEdge e) only v's adjacency list
{
int v = e.from();
adj[v].add(e);
}
11
fi
fi
Single-source shortest paths API

Goal. Find the shortest path from s to every other vertex.

public class SP

SP(EdgeWeightedDigraph G, int s) shortest paths from s in graph G

double distTo(int v) length of shortest path from s to v

Iterable <DirectedEdge> pathTo(int v) shortest path from s to v

boolean hasPathTo(int v) is there a path from s to v?

SP sp = new SP(G, s);

for (int v = 0; v < G.V(); v++)
{
StdOut.printf("%d to %d (%.2f): ", s, v, sp.distTo(v));
for (DirectedEdge e : sp.pathTo(v))
StdOut.print(e + " ");
StdOut.println();
}
12
Single-source shortest paths API

Goal. Find the shortest path from s to every other vertex.

public class SP

SP(EdgeWeightedDigraph G, int s) shortest paths from s in graph G

double distTo(int v) length of shortest path from s to v

Iterable <DirectedEdge> pathTo(int v) shortest path from s to v

boolean hasPathTo(int v) is there a path from s to v?

% java SP tinyEWD.txt 0
0 to 0 (0.00):
0 to 1 (1.05): 0->4 0.38 4->5 0.35 5->1 0.32
0 to 2 (0.26): 0->2 0.26
0 to 3 (0.99): 0->2 0.26 2->7 0.34 7->3 0.39
0 to 4 (0.38): 0->4 0.38
0 to 5 (0.73): 0->4 0.38 4->5 0.35
0 to 6 (1.51): 0->2 0.26 2->7 0.34 7->3 0.39 3->6 0.52
0 to 7 (0.60): 0->2 0.26 2->7 0.34 13
 Generic shortest-paths algorithm

Generic algorithm (to compute SPT from s)

Initialize distTo[s] = 0 and distTo[v] = ∞ for all other vertices.

Repeat until optimality conditions are satis ed:

- Relax any edge.

Ef cient implementations. How to choose which edge to relax?

Ex 1. Dijkstra's algorithm (nonnegative weights).
Ex 2. Topological sort algorithm (no directed cycles).
Ex 3. Bellman-Ford algorithm (no negative cycles).

14
fi
fi
 S HORTEST P ATHS
‣ APIs
‣ Dijkstra's algorithm
‣ Bellman-Ford algorithm
Algorithms
R OBERT S EDGEWICK | K EVIN W AYNE

http://algs4.cs.princeton.edu
 Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

0→1 5.0
1 15 3
0→4 9.0
5 0→7 8.0
4
12
s 0 3 1→2 12.0
8 1→3 15.0
7 7 2 9
1→7 4.0

9 2→3 3.0
6 1
11 2→6 11.0
5
3→6 9.0
5
4 4→5 4.0
13
4→6 20.0
4 20 6 4→7 5.0
5→2 1.0
5→6 13.0
an edge-weighted digraph 7→5 6.0
7→2 7.0
16
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -

0 1
2
7 2 3
4
5
5 6
7

4 6

choose source vertex 0

17
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.
∞
1 3
v distTo[] edgeTo[]
0 5 0 0.0 -

0 1
8 ∞ 2
7 2 3
9 4
5
5 6
7

4 6

relax all edges pointing from 0

18
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.
∞ 5

1 3
v distTo[] edgeTo[]
0 5 0 0.0 -

0 1 5.0 0→1
8 ∞ 8 2
7 2 3
9 4 9.0 0→4
5
5 6
7 8.0 0→7

4 6

∞ 9

relax all edges pointing from 0

19
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -

0 1 5.0 0→1
2
7 2 3
4 9.0 0→4
5
5 6
7 8.0 0→7

4 6

20
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -

0 1 5.0 0→1
2
7 2 3
4 9.0 0→4
5
5 6
7 8.0 0→7

4 6

choose vertex 1

21
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.
5 ∞
1 15 3
v distTo[] edgeTo[]
0 0.0 -
4
12 1 5.0 0→1
0
8 2
7 2 ∞ 3
4 9.0 0→4
5
5 6
7 8.0 0→7

4 6

relax all edges pointing from 1

22
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.
5 ∞ 20
1 15 3
v distTo[] edgeTo[]
0 0.0 -
4
12 1 5.0 0→1
0
8 2 17.0 1→2
7 2 ∞ 17 3 20.0 1→3
4 9.0 0→4
5
5 6
7 8.0 ✔
0→7

4 6

relax all edges pointing from 1

23
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -

0 1 5.0 0→1
2 17.0 1→2
7 2 3 20.0 1→3
4 9.0 0→4
5
5 6
7 8.0 0→7

4 6

24
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -

0 1 5.0 0→1
2 17.0 1→2
7 2 3 20.0 1→3
4 9.0 0→4
5
5 6
7 8.0 0→7

4 6

choose vertex 7

25
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -

0 1 5.0 0→1

8 2 17.0 1→2
7 17
7 2 3 20.0 1→3
4 9.0 0→4
6
5
5 6

∞ 7 8.0 0→7

4 6

relax all edges pointing from 7

26
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -

0 1 5.0 0→1

8 2 15.0 7→2
7 17 15
7 2 3 20.0 1→3
4 9.0 0→4
6
5 14.0 7→5
5 6

∞ 7 8.0 0→7
14
4 6

relax all edges pointing from 7

27
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -

0 1 5.0 0→1
2 15.0 7→2
7 2 3 20.0 1→3
4 9.0 0→4
5 14.0 7→5
5 6
7 8.0 0→7

4 6

28
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -

0 1 5.0 0→1
2 15.0 7→2
7 2 3 20.0 1→3
4 9.0 0→4
5 14.0 7→5
5 6
7 8.0 0→7

4 6

select vertex 4

29
 Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -

0 1 5.0 0→1

8 2 15.0 7→2
7 2 3 20.0 1→3
4 9.0 0→4
5 14.0 7→5
5
5 14 6
4 7 8.0 0→7

9 4 20 6 ∞

relax all edges pointing from 4

30
 Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -

0 1 5.0 0→1

8 2 15.0 7→2
7 2 3 20.0 1→3
4 9.0 0→4
5 13.0 4→5
5
5 14 13 6 29.0 4→6
4 7 8.0 ✔
0→7

9 4 20 6 ∞ 29

relax all edges pointing from 4

31
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -

0 1 5.0 0→1
2 15.0 7→2
7 2 3 20.0 1→3
4 9.0 0→4
5 13.0 4→5
5 6 29.0 4→6
7 8.0 0→7

4 6

32
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -

0 1 5.0 0→1
2 15.0 7→2
7 2 3 20.0 1→3
4 9.0 0→4
5 13.0 4→5
5 6 29.0 4→6
7 8.0 0→7

4 6

select vertex 5

33
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -

0 1 5.0 0→1
2 15.0 7→2
7 2 15 3 20.0 1→3
4 9.0 0→4
1
5 13.0 4→5
5 6 29.0 4→6
13 7 8.0 0→7
13
4 6 29

relax all edges pointing from 5

34
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -

0 1 5.0 0→1
2 14.0 5→2
7 2 15 14 3 20.0 1→3
4 9.0 0→4
1
5 13.0 4→5
5 6 26.0 5→6
13 7 8.0 0→7
13
4 6 29 26

relax all edges pointing from 5

35
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -

0 1 5.0 0→1
2 14.0 5→2
7 2 3 20.0 1→3
4 9.0 0→4
5 13.0 4→5
5 6 26.0 5→6
7 8.0 0→7

4 6

36
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -

0 1 5.0 0→1
2 14.0 5→2
7 2 3 20.0 1→3
4 9.0 0→4
5 13.0 4→5
5 6 26.0 5→6
7 8.0 0→7

4 6

select vertex 2

37
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.
20

1 3
v distTo[] edgeTo[]
0 0.0 -

0 3 1 5.0 0→1
2 14.0 5→2
7 2 14 3 20.0 1→3
4 9.0 0→4
11 5 13.0 4→5
5 6 26.0 5→6
7 8.0 0→7

4 6 26

relax all edges pointing from 2

38
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.
20 17

1 3
v distTo[] edgeTo[]
0 0.0 -

0 3 1 5.0 0→1
2 14.0 5→2
7 2 14 3 17.0 2→3
4 9.0 0→4
11 5 13.0 4→5
5 6 25.0 2→6
7 8.0 0→7

4 6 26 25

relax all edges pointing from 2

39
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -

0 1 5.0 0→1
2 14.0 5→2
7 2 3 17.0 2→3
4 9.0 0→4
5 13.0 4→5
5 6 25.0 2→6
7 8.0 0→7

4 6

40
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -

0 1 5.0 0→1
2 14.0 5→2
7 2 3 17.0 2→3
4 9.0 0→4
5 13.0 4→5
5 6 25.0 2→6
7 8.0 0→7

4 6

select vertex 3

41
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.
20

1 3
v distTo[] edgeTo[]
0 0.0 -

0 1 5.0 0→1
2 14.0 5→2
7 2 9
3 17.0 2→3
4 9.0 0→4
5 13.0 4→5
5 6 25.0 2→6
7 8.0 0→7

4 6 25

relax all edges pointing from 3

42
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.
20

1 3
v distTo[] edgeTo[]
0 0.0 -

0 1 5.0 0→1
2 14.0 5→2
7 2 9
3 17.0 2→3
4 9.0 0→4
5 13.0 4→5
5 6 25.0 ✔
2→6
7 8.0 0→7

4 6 25

relax all edges pointing from 3

43
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -

0 1 5.0 0→1
2 14.0 5→2
7 2 3 17.0 2→3
4 9.0 0→4
5 13.0 4→5
5 6 25.0 2→6
7 8.0 0→7

4 6

44
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -

0 1 5.0 0→1
2 14.0 5→2
7 2 3 17.0 2→3
4 9.0 0→4
5 13.0 4→5
5 6 25.0 2→6
7 8.0 0→7

4 6

select vertex 6

45
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -

0 1 5.0 0→1
2 14.0 5→2
7 2 3 17.0 2→3
4 9.0 0→4
5 13.0 4→5
5 6 25.0 2→6
7 8.0 0→7

4 6

relax all edges pointing from 6

46
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -

0 1 5.0 0→1
2 14.0 5→2
7 2 3 17.0 2→3
4 9.0 0→4
5 13.0 4→5
5 6 25.0 2→6
7 8.0 0→7

4 6

47
 Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -
s 0 1 5.0 0→1
2 14.0 5→2
7 2 3 17.0 2→3
4 9.0 0→4
5 13.0 4→5
5 6 25.0 2→6
7 8.0 0→7

4 6

shortest-paths tree from vertex s

48
Dijkstra's algorithm visualization

49
Dijkstra's algorithm visualization

50
Dijkstra's algorithm: correctness proof 1

Proposition. Dijkstra's algorithm computes a SPT in any edge-weighted digraph

with nonnegative weights.

Pf.
Each edge e = v→w is relaxed exactly once (when vertex v is relaxed),
leaving distTo[w] ≤ distTo[v] + e.weight().
Inequality holds until algorithm terminates because:
– distTo[w] cannot increase distTo[] values are monotone decreasing

– distTo[v] will not change we choose lowest distTo[] value at each step
(and edge weights are nonnegative)

Thus, upon termination, shortest-paths optimality conditions hold. 

51
Dijkstra's algorithm: Java implementation

public class DijkstraSP

{
private DirectedEdge[] edgeTo;
private double[] distTo;
private IndexMinPQ<Double> pq;

public DijkstraSP(EdgeWeightedDigraph G, int s)

{
edgeTo = new DirectedEdge[G.V()];
distTo = new double[G.V()];
pq = new IndexMinPQ<Double>(G.V());

for (int v = 0; v < G.V(); v++)

distTo[v] = Double.POSITIVE_INFINITY; relax vertices in order
distTo[s] = 0.0; of distance from s

pq.insert(s, 0.0);
while (!pq.isEmpty())
{
int v = pq.delMin();
for (DirectedEdge e : G.adj(v)) 52
Dijkstra's algorithm: Java implementation

private void relax(DirectedEdge e)

{
int v = e.from(), w = e.to();
if (distTo[w] > distTo[v] + e.weight())
{
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e; update PQ

if (pq.contains(w)) pq.decreaseKey(w, distTo[w]);

else pq.insert (w, distTo[w]);
}
}

53
Dijkstra's algorithm: which priority queue?

Depends on PQ implementation: V insert, V delete-min, E decrease-key.

PQ implementation insert delete-min decrease-key total

unordered array 1 V 1 V2

binary heap log V log V log V E log V

d-way heap logd V d logd V logd V E logE/V V

Fibonacci heap
1† log V † 1† E + V log V

† amortized

Bottom line.
Array implementation optimal for dense graphs.
Binary heap much faster for sparse graphs.
4-way heap worth the trouble in performance-critical situations.
Fibonacci heap best in theory, but not worth implementing.
54
 S HORTEST P ATHS
‣ APIs
‣ Dijkstra's algorithm
‣ Bellman-Ford algorithm
Algorithms
R OBERT S EDGEWICK | K EVIN W AYNE

http://algs4.cs.princeton.edu
Shortest paths with negative weights: failed attempts

Dijkstra. Doesn’t work with negative edge weights.

0 6 1

Dijkstra selects vertex 3 immediately after 0.

2 4 -8
But shortest path from 0 to 3 is 0→1→2→3.

3 3 2

Re-weighting. Add a constant to every edge weight doesn’t work.

0 14 1

Adding 8 to each edge weight changes the

10 12 0 shortest path from 0→1→2→3 to 0→3.

3 11 2

Conclusion. Need a different algorithm.

56
Negative cycles

Def. A negative cycle is a directed cycle whose sum of edge weights is negative.

digraph
4->5 0.35
s
5->4 -0.66
4->7 0.37
5->7 0.28
7->5 0.28
5->1 0.32
0->4 0.38
0->2 0.26
7->3 0.39
1->3 0.29 negative cycle (-0.66 + 0.37 + 0.28)
2->7 0.34 5->4->7->5
6->2 0.40
3->6 0.52
6->0 0.58 shortest path from 0 to 6
6->4 0.93 0->4->7->5->4->7->5...->1->3->6

An edge-weighted digraph with a negative cycle

Proposition. A SPT exists iff no negative cycles.

assuming all vertices reachable from s

57
Bellman-Ford algorithm

Bellman-Ford algorithm

Initialize distTo[s] = 0 and distTo[v] = ∞ for all other vertices.

Repeat V times:
- Relax each edge.

for (int i = 0; i < G.V(); i++)

for (int v = 0; v < G.V(); v++)
pass i (relax each edge)
for (DirectedEdge e : G.adj(v))
relax(e);

58
 Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

0→1 5.0

0→4 9.0

0→7 8.0
1 15 3
1→2 12.0
5
4 1→3 15.0
12
s 0 3
8 1→7 4.0
7 2 9
7 2→3 3.0
9 6 2→6 11.0
1
11
5 3→6 9.0
5
4 4→5 4.0
13
4→6 20.0
4 20 6
4→7 5.0

5→2 1.0
an edge-weighted digraph
5→6 13.0

7→5 6.0
59
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1
2
7 2 3
4
5
5 6
7

4 6

initialize

60
 Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

distTo[1]
∞
1 3
distTo[0] v distTo[] edgeTo[]
0 5 0 0.0 -
0 1
2
7 2 3
4
5
5 6
7

4 6

pass 0

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
61
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

∞ 5
1 3
v distTo[] edgeTo[]
0 5 0 0.0 -
0 1 5.0 0→1
2
7 2 3
4
5
5 6
7

4 6

pass 0

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
62
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 0 0.0 -
0 1 5.0 0→1
2
7 2 3
9 4
5
5 6
7

4 6

pass 0

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
63
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 0 0.0 -
0 1 5.0 0→1
2
7 2 3
9 4 9.0 0→4
5
5 6
7

4 6

∞ 9

pass 0

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
64
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 0 0.0 -
0 1 5.0 0→1
8 ∞ 2
7 2 3
4 9.0 0→4
5
5 6
7

4 6

pass 0

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
65
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 0 0.0 -
0 1 5.0 0→1
8 ∞ 8 2
7 2 3
4 9.0 0→4
5
5 6
7 8.0 0→7

4 6

pass 0

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
66
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

5
1 3
v distTo[] edgeTo[]
0 0.0 -
12 1 5.0 0→1
0
2
7 2 ∞ 3
4 9.0 0→4
5
5 6
7 8.0 0→7

4 6

pass 0

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
67
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

5
1 3
v distTo[] edgeTo[]
0 0.0 -
12 1 5.0 0→1
0
2 17.0 1→2
7 2 ∞ 17 3
4 9.0 0→4
5
5 6
7 8.0 0→7

4 6

pass 0

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
68
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

5 ∞
1 15 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 17.0 1→2
7 2 3
4 9.0 0→4
5
5 6
7 8.0 0→7

4 6

pass 0

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
69
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

5 ∞ 20
1 15 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 17.0 1→2
7 2 3 20.0 1→3
4 9.0 0→4
5
5 6
7 8.0 0→7

4 6

pass 0

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
70
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

5
1 3
v distTo[] edgeTo[]

4 0 0.0 -
0 1 5.0 0→1

8 2 17.0 1→2
7 2 3 20.0 1→3
4 9.0 0→4
5
5 6
7 8.0 0→7

4 6

pass 0

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
71
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

20
1 3
v distTo[] edgeTo[]
0 0.0 -
0 3 1 5.0 0→1
2 17.0 1→2
7 2 17 3 20.0 1→3
4 9.0 0→4
5
5 6
7 8.0 0→7

4 6

pass 0

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
72
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 17.0 1→2
7 2 17 3 20.0 1→3
4 9.0 0→4
11 5
5 6
7 8.0 0→7

4 6 ∞

pass 0

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
73
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 17.0 1→2
7 2 17 3 20.0 1→3
4 9.0 0→4
11 5
5 6 28.0 2→6
7 8.0 0→7

4 6 ∞ 28

pass 0

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
74
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

20
1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 17.0 1→2
7 2 9
3 20.0 1→3
4 9.0 0→4
5
5 6 28.0 2→6
7 8.0 0→7

4 6 28

pass 0

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
75
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 17.0 1→2
7 2 3 20.0 1→3
4 9.0 0→4
5
5 6 28.0 2→6
4
∞ 7 8.0 0→7

4 6

pass 0

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
76
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 17.0 1→2
7 2 3 20.0 1→3
4 9.0 0→4
5 13.0 4→5
5 6 28.0 2→6
4
∞ 13 7 8.0 0→7

4 6

pass 0

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
77
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 17.0 1→2
7 2 3 20.0 1→3
4 9.0 0→4
5 13.0 4→5
5 6 28.0 2→6
7 8.0 0→7

4 20 6

9 28

pass 0

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
78
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1

8 2 17.0 1→2
7 2 3 20.0 1→3
4 9.0 0→4
5 13.0 4→5
5
5 6 28.0 2→6
7 8.0 0→7

4 6

pass 0

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
79
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 17.0 1→2
7 2 17 3 20.0 1→3
4 9.0 0→4
1
5 13.0 4→5
5 6 28.0 2→6

13 7 8.0 0→7

4 6

pass 0

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
80
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 14.0 5→2
7 2 17 14 3 20.0 1→3
4 9.0 0→4
1
5 13.0 4→5
5 6 28.0 2→6

13 7 8.0 0→7

4 6

pass 0

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
81
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 14.0 5→2
7 2 3 20.0 1→3
4 9.0 0→4
5 13.0 4→5
5 6 28.0 2→6
13 7 8.0 0→7
13
4 6 28

pass 0

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
82
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 14.0 5→2
7 2 3 20.0 1→3
4 9.0 0→4
5 13.0 4→5
5 6 26.0 5→6
13 7 8.0 0→7
13
4 6 28 26

pass 0

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
83
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
8 2 14.0 5→2
7 2 3 20.0 1→3

6 4 9.0 0→4
5 13.0 4→5
5 6 26.0 5→6

13 7 8.0 0→7

4 6

pass 0

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
84
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
8 2 14.0 5→2
7 7 2 14 3 20.0 1→3
4 9.0 0→4
5 13.0 4→5
5 6 26.0 5→6
7 8.0 0→7

4 6

pass 0

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
85
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 5 0 0.0 -
0 1 5.0 0→1
2 14.0 5→2
7 2 3 20.0 1→3
4 9.0 0→4
5 13.0 4→5
5 6 26.0 5→6
7 8.0 0→7

4 6

pass 1

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
86
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 0 0.0 -
0 1 5.0 0→1
2 14.0 5→2
7 2 3 20.0 1→3
9 4 9.0 0→4
5 13.0 4→5
5 6 26.0 5→6
7 8.0 0→7

4 6

pass 1

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
87
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 0 0.0 -
0 1 5.0 0→1
8 8 2 14.0 5→2
7 2 3 20.0 1→3
4 9.0 0→4
5 13.0 4→5
5 6 26.0 5→6
7 8.0 0→7

4 6

pass 1

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
88
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

5
1 3
v distTo[] edgeTo[]
0 0.0 -
12 1 5.0 0→1
0
2 14.0 5→2
7 2 14 3 20.0 1→3
4 9.0 0→4
5 13.0 4→5
5 6 26.0 5→6
7 8.0 0→7

4 6

pass 1

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
89
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

5 20
1 15 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 14.0 5→2
7 2 3 20.0 1→3
4 9.0 0→4
5 13.0 4→5
5 6 26.0 5→6
7 8.0 0→7

4 6

pass 1

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
90
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

5
1 3
v distTo[] edgeTo[]

4 0 0.0 -
0 1 5.0 0→1

8 2 14.0 5→2
7 2 3 20.0 1→3
4 9.0 0→4
5 13.0 4→5
5 6 26.0 5→6
7 8.0 0→7

4 6

pass 1

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
91
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

20
1 3
v distTo[] edgeTo[]
0 0.0 -
0 3 1 5.0 0→1
2 14.0 5→2
7 2 14 3 20.0 1→3
4 9.0 0→4
5 13.0 4→5
5 6 26.0 5→6
7 8.0 0→7

4 6

pass 1

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
92
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

2-3 successfully relaxed
in pass 1, but not pass 0

20 17
1 3
v distTo[] edgeTo[]
0 0.0 -
0 3 1 5.0 0→1
2 14.0 5→2
7 2 14 3 17.0 2→3
4 9.0 0→4
5 13.0 4→5
5 6 26.0 5→6
7 8.0 0→7

4 6

pass 1

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
93
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 14.0 5→2
7 2 14 3 17.0 2→3
4 9.0 0→4
11 5 13.0 4→5
5 6 26.0 5→6
7 8.0 0→7

4 6 26

pass 1

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
94
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

2-6 successfully relaxed
in pass 0 and pass 1

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 14.0 5→2
7 2 14 3 17.0 2→3
4 9.0 0→4
11 5 13.0 4→5
5 6 25.0 2→6
7 8.0 0→7

4 6 26 25

pass 1

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
95
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

17
1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 14.0 5→2
7 2 9
3 17.0 2→3
4 9.0 0→4
5 13.0 4→5
5 6 25.0 2→6
7 8.0 0→7

4 6 25

pass 1

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
96
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 14.0 5→2
7 2 3 17.0 2→3
4 9.0 0→4
5 13.0 4→5
5 6 25.0 2→6
4
13 7 8.0 0→7

4 6

pass 1

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
97
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 14.0 5→2
7 2 3 17.0 2→3
4 9.0 0→4
5 13.0 4→5
5 6 25.0 2→6
7 8.0 0→7

4 20 6

9 25

pass 1

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
98
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1

8 2 14.0 5→2
7 2 3 17.0 2→3
4 9.0 0→4
5 13.0 4→5
5
5 6 25.0 2→6
7 8.0 0→7

4 6

pass 1

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
99
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 14.0 5→2
7 2 14 3 17.0 2→3
4 9.0 0→4
1
5 13.0 4→5
5 6 25.0 2→6

13 7 8.0 0→7

4 6

pass 1

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
100
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 14.0 5→2
7 2 3 17.0 2→3
4 9.0 0→4
5 13.0 4→5
5 6 25.0 2→6
13 7 8.0 0→7
13
4 6 25

pass 1

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
101
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
8 2 14.0 5→2
7 2 3 17.0 2→3

6 4 9.0 0→4
5 13.0 4→5
5 6 25.0 2→6

13 7 8.0 0→7

4 6

pass 1

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
102
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
8 2 14.0 5→2
7 7 2 14 3 17.0 2→3
4 9.0 0→4
5 13.0 4→5
5 6 25.0 2→6
7 8.0 0→7

4 6

pass 1

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
103
Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 14.0 5→2
7 2 3 17.0 2→3
4 9.0 0→4
5 13.0 4→5
5 6 25.0 2→6
7 8.0 0→7

4 6

pass 2, 3, 4, 5, 6, 7 (no further changes)

0→1 0→4 0→7 1→2 1→3 1→7 2→3 2→6 3→6 4→5 4→6 4→7 5→2 5→6 7→5 7→2
104
 Bellman-Ford algorithm demo

Repeat V times: relax all E edges.

1 3
v distTo[] edgeTo[]
0 0.0 -
s 0 1 5.0 0→1
2 14.0 5→2
7 2 3 17.0 2→3
4 9.0 0→4
5 13.0 4→5
5 6 25.0 2→6
7 8.0 0→7

4 6

shortest-paths tree from vertex s

105
Bellman-Ford algorithm: visualization

passes
4 7 10

13 SPT

Bellman-Ford (250 vertices)

106
Bellman-Ford algorithm: analysis

Bellman-Ford algorithm

Initialize distTo[s] = 0 and distTo[v] = ∞ for all other vertices.

Repeat V times:
- Relax each edge.

Proposition. Dynamic programming algorithm computes SPT in any edge-weighted

digraph with no negative cycles in time proportional to E × V.

Pf idea. After pass i, found shortest path to each vertex v for which the shortest
path from s to v contains i edges (or fewer).

107
Bellman-Ford algorithm: practical improvement

Observation. If distTo[v] does not change during pass i,

no need to relax any edge pointing from v in pass i+1.

FIFO implementation. Maintain queue of vertices whose distTo[] changed.

be careful to keep at most one copy

of each vertex on queue (why?)

Overall effect.
The running time is still proportional to E × V in worst case.
But much faster than that in practice.

108
Bellman-Ford algorithm: Java implementation

public class BellmanFordSP

{
private double[] distTo;
private DirectedEdge[] edgeTo; queue of vertices whose
private boolean[] onQ; distTo[] value changes
private Queue<Integer> queue;

public BellmanFordSPT(EdgeWeightedDigraph G, int s)

{
distTo = new double[G.V()];
edgeTo = new DirectedEdge[G.V()]; private void relax(DirectedEdge e)
onq = new boolean[G.V()]; {
queue = new Queue<Integer>(); int v = e.from(), w = e.to();
if (distTo[w] > distTo[v] + e.weight())
for (int v = 0; v < V; v++) {
distTo[v] = Double.POSITIVE_INFINITY; distTo[w] = distTo[v] + e.weight();
distTo[s] = 0.0; edgeTo[w] = e;
if (!onQ[w])
queue.enqueue(s); {
while (!queue.isEmpty()) queue.enqueue(w);
{ onQ[w] = true;
int v = queue.dequeue(); }
onQ[v] = false; }
for (DirectedEdge e : G.adj(v)) } 109
Single source shortest-paths implementation: cost summary

algorithm restriction typical case worst case extra space

Dijkstra no negative
E log V E log V V
(binary heap) weights

Bellman-Ford EV EV V
no negative
cycles
Bellman-Ford
E+V EV V
(queue-based)

Remark 1. Negative weights make the problem harder.

Remark 2. Negative cycles makes the problem intractable.

110