MH 3400
ALGORITHMS
FOR THE REAL WORLD
Thomas PEYRIN
Lecture 9: Shortest Paths
Algorithms for the Real World Lecture 9
Shortest Paths: transportation (MRT)
Shortest Paths
Singapore MRT/LRT map
Vertex: MRT/LRT station
Edge: MRT/LRT track
Algorithms for the Real World Lecture 9
Shortest Paths: transportation (roads)
Shortest Paths
Paris - Google Maps
Vertex: point of interest
Edge: roads
Algorithms for the Real World Lecture 9
Shortest Paths: path finding in games
Shortest Paths
Pacman game
Vertex: tiles in the
game map
Edge: connections
between tiles
Algorithms for the Real World Lecture 9
Shortest Paths: currency or stocks arbitrage
Shortest Paths
Currency exchange rates table example
Vertex: currencies/stocks
Edge: conversion rates
Goal: find negative cycle
1 USD => 0.76904 GBP => 0.92307 EUR => 1.00001 USD
Algorithms for the Real World Lecture 9
Shortest Paths: virus spreading models
Shortest Paths
Donker et al., “Measuring distance through dense weighted
networks: The case of hospital-associated pathogens”
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5542422/
Vertex: hospitals
Edge: patient connection strength
Algorithms for the Real World Lecture 9
Weighted Graphs
A weighted graph is a graph that has a numeric label, w(ei), associated
with each edge, ei, called the weight of edge ei.
Usually the weight is a distance, a cost, etc.
Shortest Paths
A
E
B
D
C
The length or weight of a path P, in G, is the sum of the weights of the
edges of P: w(P) = σ=0
−1
The distance from a vertex v to a vertex u in G, denoted d(v, u), is the
length of a minimum length path (also called shortest path) from v to u,
if such a path exists (we have d(v, u) = +∞ otherwise)
10
7
15
8
10
9
4
With path P = A → E → D → B,
then w(P) = 21
Distance d(E,B) = 11
Reminder:
n denotes #nodes
m denotes #edges
Algorithms for the Real World Lecture 9
Weighted Graphs
A weighted graph is a graph that has a numeric label, w(ei), associated
with each edge, ei, called the weight of edge ei.
Usually the weight is a distance, a cost, etc.
Shortest Paths
A
E
B
D
C
10
7
15
8
10
9
4
Edges list
A
B
C
D
E
9
A
B
8
A
C
10
A
D
10
A
E
4
B
D
15
C
D
15
D
E
Vertices list
Reminder:
n denotes #nodes
m denotes #edges
Algorithms for the Real World Lecture 9
Weighted Graphs
A weighted graph is a graph that has a numeric label, w(ei), associated
with each edge, ei, called the weight of edge ei.
Usually the weight is a distance, a cost, etc.
Shortest Paths
A
E
B
D
C
10
7
15
8
10
9
4
A
B
C
D
E
Adjacency
list
9B 8C 10D 10E
9A 4D
8A 15D
10A 4B 15C 7E
10A 7D
Reminder:
n denotes #nodes
m denotes #edges
MH 3400 - Algorithms for the Real World
Shortest Paths
Outline
▪Single-Source Shortest Paths
▪Dijkstra’s Algorithm
▪Bellman-Ford Algorithm
▪Shortest Paths in DAG
▪All-Pairs Shortest Paths
▪Lessons Learned
Algorithms for the Real World Lecture 9 Shortest Paths
Algorithms for the Real World Lecture 9
Single-Source Shortest Paths Problem
Single-Source Shortest Paths Problem: given a graph G and a node v
from G, find the distance (shortest path) from v to all other nodes in G.
Shortest Paths
Algorithms for the Real World Lecture 9
Single-Source Shortest Paths Problem
Single-Source Shortest Paths Problem: given a graph G and a node v
from G, find the distance (shortest path) from v to all other nodes in G.
Shortest Paths
2
2
1
0
3
4
1
1
1
2
2
2
3
3
3
3
4
4
4
5
6
5
7
7
8
3
4
5
6
7
8
9
8
9
9
9
4
5
Algorithms for the Real World Lecture 9
Single-Source Shortest Paths Problem
Single-Source Shortest Paths Problem: given a graph G and a node v
from G, find the distance (shortest path) from v to all other nodes in G.
Shortest Paths
Property 1: a subpath of a shortest path is itself a shortest path
Property 2: there is a tree of shortest paths from a start node to all the
other nodes
2
2
1
0
3
4
1
1
1
2
2
2
3
3
3
3
4
4
4
5
6
5
7
7
8
3
4
5
6
7
8
9
8
9
9
9
4
5
Algorithms for the Real World Lecture 9
Single-Source Shortest Paths Problem
Single-Source Shortest Paths Problem: given a graph G and a node v
from G, find the distance (shortest path) from v to all other nodes in G.
Shortest Paths
Naïve algorithm: for all target nodes u in G, try all paths from v to u
and keep the shortest one.
Problem: there is an exponential number of paths (in terms of number
of edges m) between two nodes.
Algorithms for the Real World Lecture 9
Breadth-First Search (BFS)
When all weights in the graph are equal to 1 (or all positive and
equal), we can use BFS.
BFS algorithm allows to find all shortest paths from a source node with
complexity O(n+m) for n nodes and m edges.
Shortest Paths
1
0 2
1
2
BFS
Algorithms for the Real World Lecture 9
Breadth-First Search (BFS)
Shortest Paths
2
2
1
0
3
4
1
1
1
2
2
2
3
3
3
3
4
4
4
4
5
5
6
6
7
3
4
5
6
7
8
9
8
9
9
9
4
5
Is () = 1 for all i really matching practical problems ?
Number of hops ≠ distance
When all weights in the graph are equal to 1 (or all positive and
equal), we can use BFS.
BFS algorithm allows to find all shortest paths from a source node with
complexity O(n+m) for n nodes and m edges.
MH 3400 - Algorithms for the Real World
Shortest Paths
Outline
▪Single-Source Shortest Paths
▪Dijkstra’s Algorithm
▪Bellman-Ford Algorithm
▪Shortest Paths in DAG
▪All-Pairs Shortest Paths
▪Lessons Learned
Algorithms for the Real World Lecture 9 Shortest Paths
Algorithms for the Real World Lecture 9
Why Dijkstra’s Algorithm ?
What if the weights of the edges are different ?
Then BFS does not necessarily finds the shortest paths.
Shortest Paths
10
0 12
6
20
10 10
6 10
3
1
2
9
0 7
6
16
Algorithms for the Real World Lecture 9
Why Dijkstra’s Algorithm ?
Dijkstra’s algorithm can be seen as a “weighted” generalization of
BFS. If all weights are equal, then Dijkstra = BFS. A alternative way to
consider Dijkstra’s algorithm is to view it as a greedy method.
Shortest Paths
When all the edge weights are potentially different, but non-negative
(w(ei) ≥ 0 for all i), we can use Dijkstra’s algorithm
When all the edge weights are non-negative, we know that there are no
negative-weight cycles in G.
Algorithms for the Real World Lecture 9
General Idea of Dijkstra’s Algorithm
Dijkstra Algorithm: from the start node s, we grow a cloud of nodes
(initialized with s), until the cloud contains all nodes. How do we pick the
next node to be added in the cloud ? We simply take the closest
adjacent node from the cloud (greedy criterion).
Shortest Paths
How: D[v] represents the distance of v from s in the subgraph consisting of the
cloud and its adjacent vertices. At each step, we add to the cloud the vertex u
outside the cloud with the smallest distance label D[u] and we update the labels
of the vertices adjacent to u.
Assumption: the graph edge weights are non-negative
Algorithms for the Real World Lecture 9
Example for Dijkstra’s Algorithm
Shortest Paths
A
S
C
B
D
10
10
6
103
1
2
E
5
4
Dijkstra Algorithm: from the start node s, we grow a cloud of nodes
(initialized with s), until the cloud contains all nodes. How do we pick the
next node to be added in the cloud ? We simply take the closest
adjacent node from the cloud (greedy criterion).
How: D[v] represents the distance of v from s in the subgraph consisting of the
cloud and its adjacent vertices. At each step, we add to the cloud the vertex u
outside the cloud with the smallest distance label D[u] and we update the labels
of the vertices adjacent to u.
Algorithms for the Real World Lecture 9
Example for Dijkstra’s Algorithm
Shortest Paths
A
S
C
B
D
10
10
6
103
1
2
E
5
4
Dijkstra Algorithm: from the start node s, we grow a cloud of nodes
(initialized with s), until the cloud contains all nodes. How do we pick the
next node to be added in the cloud ? We simply take the closest
adjacent node from the cloud (greedy criterion).
How: D[v] represents the distance of v from s in the subgraph consisting of the
cloud and its adjacent vertices. At each step, we add to the cloud the vertex u
outside the cloud with the smallest distance label D[u] and we update the labels
of the vertices adjacent to u.
D = [S:∞, A:∞, B:∞, C:∞, D:∞, E:∞]
Initialize D table
Algorithms for the Real World Lecture 9
Example for Dijkstra’s Algorithm
Shortest Paths
D = [S:0, A:10, B:6, C:∞, D:∞, E:∞]
Dijkstra Algorithm: from the start node s, we grow a cloud of nodes
(initialized with s), until the cloud contains all nodes. How do we pick the
next node to be added in the cloud ? We simply take the closest
adjacent node from the cloud (greedy criterion).
How: D[v] represents the distance of v from s in the subgraph consisting of the
cloud and its adjacent vertices. At each step, we add to the cloud the vertex u
outside the cloud with the smallest distance label D[u] and we update the labels
of the vertices adjacent to u.
A
S
C
B
D
10
10
6
103
1
2
E
5
4
Start from S and update D table
Algorithms for the Real World Lecture 9
Example for Dijkstra’s Algorithm
Shortest Paths
D = [S:0, A:9, B:6, C:7, D:16, E:11]
Dijkstra Algorithm: from the start node s, we grow a cloud of nodes
(initialized with s), until the cloud contains all nodes. How do we pick the
next node to be added in the cloud ? We simply take the closest
adjacent node from the cloud (greedy criterion).
How: D[v] represents the distance of v from s in the subgraph consisting of the
cloud and its adjacent vertices. At each step, we add to the cloud the vertex u
outside the cloud with the smallest distance label D[u] and we update the labels
of the vertices adjacent to u.
A
S
C
B
D
10
10
6
103
1
2
E
5
4
B is the closest adjacent node,
select it and update the D table
Algorithms for the Real World Lecture 9
Example for Dijkstra’s Algorithm
Shortest Paths
D = [S:0, A:9, B:6, C:7, D:16, E:11]
Dijkstra Algorithm: from the start node s, we grow a cloud of nodes
(initialized with s), until the cloud contains all nodes. How do we pick the
next node to be added in the cloud ? We simply take the closest
adjacent node from the cloud (greedy criterion).
How: D[v] represents the distance of v from s in the subgraph consisting of the
cloud and its adjacent vertices. At each step, we add to the cloud the vertex u
outside the cloud with the smallest distance label D[u] and we update the labels
of the vertices adjacent to u.
A
S
C
B
D
10
10
6
103
1
2
E
5
4
C is the closest adjacent node,
select it and update the D table
Algorithms for the Real World Lecture 9
Example for Dijkstra’s Algorithm
Shortest Paths
D = [S:0, A:9, B:6, C:7, D:16, E:11]
Dijkstra Algorithm: from the start node s, we grow a cloud of nodes
(initialized with s), until the cloud contains all nodes. How do we pick the
next node to be added in the cloud ? We simply take the closest
adjacent node from the cloud (greedy criterion).
How: D[v] represents the distance of v from s in the subgraph consisting of the
cloud and its adjacent vertices. At each step, we add to the cloud the vertex u
outside the cloud with the smallest distance label D[u] and we update the labels
of the vertices adjacent to u.
A
S
C
B
D
10
10
6
103
1
2
E
5
4
A is the closest adjacent node,
select it and update the D table
Algorithms for the Real World Lecture 9
Example for Dijkstra’s Algorithm
Shortest Paths
D = [S:0, A:9, B:6, C:7, D:15, E:11]
Dijkstra Algorithm: from the start node s, we grow a cloud of nodes
(initialized with s), until the cloud contains all nodes. How do we pick the
next node to be added in the cloud ? We simply take the closest
adjacent node from the cloud (greedy criterion).
How: D[v] represents the distance of v from s in the subgraph consisting of the
cloud and its adjacent vertices. At each step, we add to the cloud the vertex u
outside the cloud with the smallest distance label D[u] and we update the labels
of the vertices adjacent to u.
A
S
C
B
D
10
10
6
103
1
2
E
5
4
E is the closest adjacent node,
select it and update the D table
Algorithms for the Real World Lecture 9
Example for Dijkstra’s Algorithm
Shortest Paths
D = [S:0, A:9, B:6, C:7, D:15, E:11]
Dijkstra Algorithm: from the start node s, we grow a cloud of nodes
(initialized with s), until the cloud contains all nodes. How do we pick the
next node to be added in the cloud ? We simply take the closest
adjacent node from the cloud (greedy criterion).
How: D[v] represents the distance of v from s in the subgraph consisting of the
cloud and its adjacent vertices. At each step, we add to the cloud the vertex u
outside the cloud with the smallest distance label D[u] and we update the labels
of the vertices adjacent to u.
A
S
C
B
D
10
10
6
103
1
2
E
5
4
D is the closest adjacent node,
select it and we are finished !
Algorithms for the Real World Lecture 9
Example for Dijkstra’s Algorithm
Shortest Paths
D = [S:0, A:9, B:6, C:7, D:15, E:11]
Dijkstra Algorithm: from the start node s, we grow a cloud of nodes
(initialized with s), until the cloud contains all nodes. How do we pick the
next node to be added in the cloud ? We simply take the closest
adjacent node from the cloud (greedy criterion).
How: D[v] represents the distance of v from s in the subgraph consisting of the
cloud and its adjacent vertices. At each step, we add to the cloud the vertex u
outside the cloud with the smallest distance label D[u] and we update the labels
of the vertices adjacent to u.
D gives the final distance tableA
S
C
B
D
10
10
6
103
1
2
E
5
4
Algorithms for the Real World Lecture 9
Example for Dijkstra’s Algorithm
Shortest Paths
Dijkstra's algorithm runtime - Wikipedia
Algorithms for the Real World Lecture 9
Example for Dijkstra’s Algorithm
Shortest Paths
Dijkstra's algorithm runtime - Wikipedia
Algorithms for the Real World Lecture 9
Example for Dijkstra’s Algorithm
Shortest Paths
Dijkstra's algorithm runtime - Wikipedia
Algorithms for the Real World Lecture 9
Pseudo-code for Dijkstra’s Algorithm
Shortest Paths
Shortest_Path_Dijkstra(G,s)
D[i] = ∞ for all vertices i #init of D table
D[s] = 0
cloud[i] = False for all vertices i #init of cloud
for i in [0,n-1]:
v  closest unvisited vertex
cloud[v] = True
for all outgoing edges (v,b;w) from v:
if cloud[b] = False:
if D[v] + w < D[b]: D[b] = D[v] + w
if all unvisited nodes are at distance ∞: break
return D
Python implementation of Dijkstra for the lab session
Algorithms for the Real World Lecture 9
Correctness of Dijkstra’s Algorithm
Lemma: in Dijkstra’s algorithm, whenever a vertex u is pulled into
the cloud, D[u] is equal to the length of a shortest path from v to u.
Shortest Paths
u
Proof:
Let u be the first wrong vertex the algorithm processed (D[u] does not
contain the shortest path length for node u when u is added in the
cloud): D[u] > d(s,u)
Let z be the first vertex in the real shortest path from s to u that was not
in the cloud when u was inserted in the cloud.
Let y be the previous node of z on the true shortest path. Since u is the
first wrong vertex, z distance is valid: D[z] = d(s,z)
We have D[u] ≤ D[z] when we added u in the cloud (otherwise z would
have been added in the cloud instead of u):
D[u] ≤ D[z] = d(s,z) ≤ d(s,z) + d(z,u) (because any distance is positive
since we assumed no negative edge in the graph).
Then d(s,z) + d(z,u) = d(s,u) because a subpath of a shortest path is
itself a shortest path.
Finally, we get D[u] ≤ d(s,u) which contradicts the definition of u.
S
y
z
D[u] > d(s,u)
D[y] = d(s,y)
D[z] = d(s,z)
Algorithms for the Real World Lecture 9
Dijkstra’s Algorithm with Negative Weights
Why Dijkstra’s algorithm doesn’t work with negative weights ?
=> Because if a node with a negative incident edge were to be added
late to the cloud, it could mess up distances for vertices already in the
cloud.
Shortest Paths
D = [S:0, A:9, B:6, C:7, D:16, E:11]
A
S
C
B
D
10
10
6
103
1
2
E
5
-14
Algorithms for the Real World Lecture 9
Dijkstra’s Algorithm with Negative Weights
Why Dijkstra’s algorithm doesn’t work with negative weights ?
=> Because if a node with a negative incident edge were to be added
late to the cloud, it could mess up distances for vertices already in the
cloud.
Shortest Paths
D = [S:0, A:9, B:6, C:7, D:-3, E:11]
A
S
C
B
D
10
10
6
103
1
2
E
5
-14
E is the closest adjacent node,
select it and update the D table
Algorithms for the Real World Lecture 9
Dijkstra’s Algorithm with Negative Weights
Why Dijkstra’s algorithm doesn’t work with negative weights ?
=> Because if a node with a negative incident edge were to be added
late to the cloud, it could mess up distances for vertices already in the
cloud.
Shortest Paths
D = [S:0, A:9, B:6, C:7, D:-3, E:11]
A
S
C
B
D
10
10
6
103
1
2
E
5
-14
D is the closest adjacent node,
select it and we are finished !
Algorithms for the Real World Lecture 9
Dijkstra’s Algorithm with Negative Weights
Why Dijkstra’s algorithm doesn’t work with negative weights ?
=> Because if a node with a negative incident edge were to be added
late to the cloud, it could mess up distances for vertices already in the
cloud.
Shortest Paths
D = [S:0, A:9, B:6, C:7, D:-3, E:11]
A
S
C
B
D
10
10
6
103
1
2
E
5
-14
D is the closest adjacent node,
select it and we are finished !
But A real distance is 7:
S → B → E → D → A
Algorithms for the Real World Lecture 9
Complexity of Dijkstra’s Algorithm
Shortest Paths
Assuming adjacency list, Dijkstra’s algorithm complexity is O(n2)
Shortest_Path_Dijkstra(G,s)
D[i] = ∞ for all vertices i
D[s] = 0
cloud[i] = False for all vertices i
for i in [0,n-1]:
v  closest unvisited vertex
cloud[v] = True
for all outgoing edges (v,b;w) from v:
if cloud[b] = False:
if D[v] + w < D[b]: D[b] = D[v] + w
if all unvisited nodes are at distance ∞: break
return D
Algorithms for the Real World Lecture 9
Complexity of Dijkstra’s Algorithm
Shortest Paths
Shortest_Path_Dijkstra(G,s)
D[i] = ∞ for all vertices i
D[s] = 0
cloud[i] = False for all vertices i
for i in [0,n-1]:
v  closest unvisited vertex
cloud[v] = True
for all outgoing edges (v,b;w) from v:
if cloud[b] = False:
if D[v] + w < D[b]: D[b] = D[v] + w
if all unvisited nodes are at distance ∞: break
return D
O(n)
Complexity = O(n) +
Assuming adjacency list, Dijkstra’s algorithm complexity is O(n2)
Algorithms for the Real World Lecture 9
Complexity of Dijkstra’s Algorithm
Shortest Paths
Shortest_Path_Dijkstra(G,s)
D[i] = ∞ for all vertices i
D[s] = 0
cloud[i] = False for all vertices i
for i in [0,n-1]:
v  closest unvisited vertex
cloud[v] = True
for all outgoing edges (v,b;w) from v:
if cloud[b] = False:
if D[v] + w < D[b]: D[b] = D[v] + w
if all unvisited nodes are at distance ∞: break
return D
Repeat
n times
O(n)
Assuming adjacency list, Dijkstra’s algorithm complexity is O(n2)
Complexity = O(n) + O(n * …)
Algorithms for the Real World Lecture 9
Complexity of Dijkstra’s Algorithm
Shortest Paths
Shortest_Path_Dijkstra(G,s)
D[i] = ∞ for all vertices i
D[s] = 0
cloud[i] = False for all vertices i
for i in [0,n-1]:
v  closest unvisited vertex
cloud[v] = True
for all outgoing edges (v,b;w) from v:
if cloud[b] = False:
if D[v] + w < D[b]: D[b] = D[v] + w
if all unvisited nodes are at distance ∞: break
return D
O(n)
(scan D
and cloud
table once)
O(n)
(scan D and
cloud table once)
Repeat
deg(v)
times
O(n)
Assuming adjacency list, Dijkstra’s algorithm complexity is O(n2)
Complexity = O(n) + O(n * (n + deg(v) +n))
Repeat
n times
Algorithms for the Real World Lecture 9
Complexity of Dijkstra’s Algorithm
Shortest Paths
O(n)
Assuming adjacency list, Dijkstra’s algorithm complexity is O(n2)
Repeat
n times
Complexity = O(n) + O(n * (n + n)) + O(m) = O(n2+m) = O(n2) since G is simple
Shortest_Path_Dijkstra(G,s)
D[i] = ∞ for all vertices i
D[s] = 0
cloud[i] = False for all vertices i
for i in [0,n-1]:
v  closest unvisited vertex
cloud[v] = True
for all outgoing edges (v,b;w) from v:
if cloud[b] = False:
if D[v] + w < D[b]: D[b] = D[v] + w
if all unvisited nodes are at distance ∞: break
return D
O(m) in total
(because we will go
once in each edge)
Algorithms for the Real World Lecture 9
Priority Queues
Shortest Paths
A priority queue is a data structure similar to a queue, but the dequeuing
is done according to a certain key value (not necessarily the first arrived)
One can implement a priority queue Q with a heap H:
- inserting an element in Q = inserting an element in H
- extracting an element from Q = extracting the minimum from H
- updating an element’s key in Q = remove and add back this element in H
Complexities of these operations:
- inserting an element in the heap costs log(n)
- extracting the minimum value from the heap costs log(n)
- updating the key of an element in the heap costs log(n)
Algorithms for the Real World Lecture 9
Dijkstra’s Algorithm with Priority Queues
Shortest Paths
We can implement the Dijkstra’s algorithm with a priority queue Q to
simulate the cloud:
• all nodes are initially added in Q and their key is updated during the algorithm if
a better path is found
• the selection of the new node to add in the cloud is done by dequeuing the
minimal element of Q
Shortest_Path_Dijkstra(G,s)
D[i] = ∞ for all vertices i
D[s] = 0
add all vertices i in Q, using D[i] as key
while Q is not empty:
v  Q.remove_min( )
for all outgoing edges (v,b;w) from v, s.t. b∈Q:
if D[v] + w < D[b]:
D[b] = D[v] + w
update key of b in Q to D[b]
return D
Algorithms for the Real World Lecture 9
Complexity of Dijkstra’s Algorithm
Shortest Paths
Assuming adjacency list and using a priority queue, Dijkstra’s
algorithm complexity is O((n+m) log(n))
Shortest_Path_Dijkstra(G,s)
D[i] = ∞ for all vertices i
D[s] = 0
add all vertices i in Q, using D[i] as key
while Q is not empty:
v  Q.remove_min( )
for all outgoing edges (v,b;w) from v, s.t. b∈Q:
if D[v] + w < D[b]:
D[b] = D[v] + w
update key of b in Q to D[b]
return D
Algorithms for the Real World Lecture 9
Complexity of Dijkstra’s Algorithm
Shortest Paths
Assuming adjacency list and using a priority queue, Dijkstra’s
algorithm complexity is O((n+m) log(n))
Shortest_Path_Dijkstra(G,s)
D[i] = ∞ for all vertices i
D[s] = 0
add all vertices i in Q, using D[i] as key
while Q is not empty:
v  Q.remove_min( )
for all outgoing edges (v,b;w) from v, s.t. b∈Q:
if D[v] + w < D[b]:
D[b] = D[v] + w
update key of b in Q to D[b]
return D
Complexity = O(n) +
O(n)
Algorithms for the Real World Lecture 9
Complexity of Dijkstra’s Algorithm
Shortest Paths
Assuming adjacency list and using a priority queue, Dijkstra’s
algorithm complexity is O((n+m) log(n))
O(n)
Shortest_Path_Dijkstra(G,s)
D[i] = ∞ for all vertices i
D[s] = 0
add all vertices i in Q, using D[i] as key
while Q is not empty:
v  Q.remove_min( )
for all outgoing edges (v,b;w) from v, s.t. b∈Q:
if D[v] + w < D[b]:
D[b] = D[v] + w
update key of b in Q to D[b]
return D
O(n log(n))
(n elements to
add, cost log(n)
per element)
Complexity = O(n) + O(n log(n))
Algorithms for the Real World Lecture 9
Complexity of Dijkstra’s Algorithm
Shortest Paths
Assuming adjacency list and using a priority queue, Dijkstra’s
algorithm complexity is O((n+m) log(n))
O(n)
Shortest_Path_Dijkstra(G,s)
D[i] = ∞ for all vertices i
D[s] = 0
add all vertices i in Q, using D[i] as key
while Q is not empty:
v  Q.remove_min( )
for all outgoing edges (v,b;w) from v, s.t. b∈Q:
if D[v] + w < D[b]:
D[b] = D[v] + w
update key of b in Q to D[b]
return D
Complexity = O(n) + O(n log(n)) + O(n log(n))
O(n log(n))
in total
(n elements to
delete in total (each
node is added and
deleted once), cost
log(n) per element)
O(n log(n))
Algorithms for the Real World Lecture 9
Complexity of Dijkstra’s Algorithm
Shortest Paths
Assuming adjacency list and using a priority queue, Dijkstra’s
algorithm complexity is O((n+m) log(n))
O(n)
Complexity = O(n) + O(n log(n)) + O(n log(n)) + O(m log(n))
= O((n+m) log(n)) = O(m log(n)) if G is connected
O(n log(n))
in total
O(n log(n))
Shortest_Path_Dijkstra(G,s)
D[i] = ∞ for all vertices i
D[s] = 0
add all vertices i in Q, using D[i] as key
while Q is not empty:
v  Q.remove_min( )
for all outgoing edges (v,b;w) from v, s.t. b∈Q:
if D[v] + w < D[b]:
D[b] = D[v] + w
update key of b in Q to D[b]
return D
O(m log(n))
in total
(because we will go
once in each edge
and each key
update costs log(n))
Algorithms for the Real World Lecture 9
Trying Dijkstra’s Algorithm
Shortest Paths
http://elearning.oms.rwth-aachen.de/Dijkstra/dijkstra.html
MH 3400 - Algorithms for the Real World
Shortest Paths
Outline
▪Single-Source Shortest Paths
▪Dijkstra’s Algorithm
▪Bellman-Ford Algorithm
▪Shortest Paths in DAG
▪All-Pairs Shortest Paths
▪Lessons Learned
Algorithms for the Real World Lecture 9 Shortest Paths
Algorithms for the Real World Lecture 9
Why Bellman-Ford’s Algorithm ?
What if we consider negative weights ? E.g. cashflow, elevation, etc.
• Dijkstra doesn’t work anymore
• The graph has to be directed (to avoid abuse with negative cycles)
Shortest Paths
Bellman-Ford will find the shortest paths from a source node s in
a graph with negative weight, with complexity O(nm).
General Idea: it does not use a greedy method. Instead, at each
iteration, it checks all edges of the graph if any relaxation is possible.
At iteration i, it will have found all shortest paths that use i edges.
A
S B
10
-6
3
D = [S:0, A:10, B:-6] D = [S:0, A:-3, B:-6]
relaxation
d(B) + w(B->A) = -6 +3 = -3
Algorithms for the Real World Lecture 9
Example for Bellman-Ford’s Algorithm
Shortest Paths
A
S
C
B
D
10
10
-6
103
1
-2
E
5
-4 D = [S:0, A:∞, B:∞, C:∞, D:∞, E:∞]
Initialize D table
General Idea: it does not use a greedy method. Instead, at each
iteration, it checks all edges of the graph if any relaxation is possible.
At iteration i, it will have found all shortest paths that use i edges.
Edges:
(S,A,10)
(S,B,-6)
(A,D,10)
(B,A,3)
(B,C,1)
(C,A,-2)
(D,B,10)
(D,E,-4)
(E,B,5)
Algorithms for the Real World Lecture 9
Example for Bellman-Ford’s Algorithm
Shortest Paths
D = [S:0, A:-7, B:-6, C:-5, D:20, E:16]
Iteration 1:
General Idea: it does not use a greedy method. Instead, at each
iteration, it checks all edges of the graph if any relaxation is possible.
At iteration i, it will have found all shortest paths that use i edges.
A
S
C
B
D
10
10
-6
103
1
-2
E
5
-4
Edges:
(S,A,10)
(S,B,-6)
(A,D,10)
(B,A,3)
(B,C,1)
(C,A,-2)
(D,B,10)
(D,E,-4)
(E,B,5)
Algorithms for the Real World Lecture 9
Example for Bellman-Ford’s Algorithm
Shortest Paths
D = [S:0, A:-7, B:-6, C:-5, D:3, E:-1]
Iteration 2:
General Idea: it does not use a greedy method. Instead, at each
iteration, it checks all edges of the graph if any relaxation is possible.
At iteration i, it will have found all shortest paths that use i edges.
A
S
C
B
D
10
10
-6
103
1
-2
E
5
-4
Edges:
(S,A,10)
(S,B,-6)
(A,D,10)
(B,A,3)
(B,C,1)
(C,A,-2)
(D,B,10)
(D,E,-4)
(E,B,5)
Algorithms for the Real World Lecture 9
Example for Bellman-Ford’s Algorithm
Shortest Paths
D = [S:0, A:-7, B:-6, C:-5, D:3, E:-1]
Iteration 3/4/5: no relaxation
Job finished !
General Idea: it does not use a greedy method. Instead, at each
iteration, it checks all edges of the graph if any relaxation is possible.
At iteration i, it will have found all shortest paths that use i edges.
A
S
C
B
D
10
10
-6
103
1
-2
E
5
-4
Edges:
(S,A,10)
(S,B,-6)
(A,D,10)
(B,A,3)
(B,C,1)
(C,A,-2)
(D,B,10)
(D,E,-4)
(E,B,5)
Algorithms for the Real World Lecture 9
Pseudo-code for Bellman-Ford’s Algorithm
Shortest Paths
Shortest_Path_Bellman_Ford(G,s)
D[i] = ∞ for all vertices i #init of D table
D[s] = 0
for i in [1,n-1]: #repeat n-1 times
for all edges (a,b;w):
if D[a] + w < D[b]: D[b] = D[a] + w #relaxation
if there are no more node left with potential relaxation:
return D
else:
return “negative cycle”
Algorithms for the Real World Lecture 9
Correctness of Bellman-Ford’s Algorithm
Shortest Paths
Lemma: if at the end of the Bellman-Ford algorithm there is an
edge (a, b) s.t. D[a] + w((a, b)) < D[b], then G contains a negative-
weight cycle. Otherwise, D[a] = d(s, a) for each vertex a in G.
Proof (part 1): let di(s, u) denote the length of the shortest path from s to
u with at most i edges. We claim that after iteration i of the main for loop,
we have D[u] = di(s, u) for each vertex in G. This is true for i=0 and
assume that it is true up to iteration i (we will now try to prove it for i+1).
We have di+1(s, u) = di(s, u) or di+1(s, u) = di(s, z) + w((z, u)) for some
vertex z in G. We do a relaxation for every edge of G in iteration i+1, so
after iteration i+1 we have D[u] = di(s, u) = di+1(s, u) if it is the former
case and we have D[u] = D[z] + w((z, u)) = di(s, z) + w((z, u)) = di+1(s, u)
if it is the latter case. Thus, if D[u] = di(s, u) for each vertex u before
iteration i+1, then D[u] = di+1(s, u) for each vertex u after iteration i+1.
Also, D[u] = dn-1(s, u) at the end of the algorithm.
Algorithms for the Real World Lecture 9
Correctness of Bellman-Ford’s Algorithm
Shortest Paths
Lemma: if at the end of the Bellman-Ford algorithm there is an
edge (a, b) s.t. D[a] + w((a, b)) < D[b], then G contains a negative-
weight cycle. Otherwise, D[a] = d(s, a) for each vertex a in G.
Proof (part 2): Now observe that if there is still an edge in G that can be
relaxed, then there is some vertex u in G, such that the n-edge distance
from s to u is less than the (n − 1)-edge distance from s to u, that is,
dn(s, u) < dn-1(s, u). Yet, there are only n vertices in G; so if there is a
shortest n-edge path from s to u, it must repeat some vertex z in G twice
(aka a cycle). Moreover, since d0(z, z) = 0), this cycle must be a
negative-weight cycle. Thus: still an edge that can be relaxed means
negative-weight cycle.
If there is no more edge in G that can be relaxed, then no negative cycle
and dn-1(s, u) = d(s, u).
Algorithms for the Real World Lecture 9
Complexity of Bellman-Ford’s Algorithm
Shortest Paths
Shortest_Path_Bellman_Ford(G,s)
D[i] = ∞ for all vertices i
D[s] = 0
for i in [1,n-1]:
for all edges (a,b;w):
if D[a] + w < D[b]: D[b] = D[a] + w
if there are no more node left with potential relaxation:
return D
else:
return “negative cycle”
Assuming adjacency list, Bellman-Ford complexity is O(mn)
Algorithms for the Real World Lecture 9
Complexity of Bellman-Ford’s Algorithm
Shortest Paths
Assuming adjacency list, Bellman-Ford complexity is O(mn)
Shortest_Path_Bellman_Ford(G,s)
D[i] = ∞ for all vertices i
D[s] = 0
for i in [1,n-1]:
for all edges (a,b;w):
if D[a] + w < D[b]: D[b] = D[a] + w
if there are no more node left with potential relaxation:
return D
else:
return “negative cycle”
Complexity = O(n) +
O(n)
Algorithms for the Real World Lecture 9
Complexity of Bellman-Ford’s Algorithm
Shortest Paths
Assuming adjacency list, Bellman-Ford complexity is O(mn)
O(n)
Shortest_Path_Bellman_Ford(G,s)
D[i] = ∞ for all vertices i
D[s] = 0
for i in [1,n-1]:
for all edges (a,b;w):
if D[a] + w < D[b]: D[b] = D[a] + w
if there are no more node left with potential relaxation:
return D
else:
return “negative cycle”
Complexity = O(n) + O(mn)
Repeat
n-1 timesO(m)
Algorithms for the Real World Lecture 9
Complexity of Bellman-Ford’s Algorithm
Shortest Paths
Assuming adjacency list, Bellman-Ford complexity is O(mn)
O(n)
Shortest_Path_Bellman_Ford(G,s)
D[i] = ∞ for all vertices i
D[s] = 0
for i in [1,n-1]:
for all edges (a,b;w):
if D[a] + w < D[b]: D[b] = D[a] + w
if there are no more node left with potential relaxation:
return D
else:
return “negative cycle”
Complexity = O(n) + O(mn) + O(m) = O(mn)
Repeat
n-1 timesO(m)
O(m)
Algorithms for the Real World Lecture 9
Complexity of Bellman-Ford’s Algorithm
Shortest Paths
Assuming adjacency list, Bellman-Ford complexity is O(mn)
O(n)
Shortest_Path_Bellman_Ford(G,s)
D[i] = ∞ for all vertices i
D[s] = 0
for i in [1,n-1]:
for all edges (a,b;w):
if D[a] + w < D[b]: D[b] = D[a] + w
if there are no more node left with potential relaxation:
return D
else:
return “negative cycle”
Complexity = O(n) + O(mn) + O(m) = O(mn)
Repeat
n-1 timesO(m)
O(m)
If no relaxation during an
iteration, you can early abort
Algorithms for the Real World Lecture 9
Detecting Negative Cycles
Shortest Paths
Currency exchange rates table example
1 USD => 0.76904 GBP => 0.92307 EUR => 1.00001 USD
Detecting negative cycle application: currency arbitrage
Vertices are currencies and edges are conversion rates.
You have an arbitrage if you find a cycle such that w1 * w2 * … * wn > 1.
How to find such a cycle ? Take the log of this inequation:
w1 * w2 * … * wn > 1  log(w1 * w2 * … * wn) > 0
 log(w1) + log(w2) + … + log(wn) > 0
 - log(w1) - log(w2) - … - log(wn) < 0
 find a negative cycle in the graph whose weights are - log(wi)
MH 3400 - Algorithms for the Real World
Shortest Paths
Outline
▪Single-Source Shortest Paths
▪Dijkstra’s Algorithm
▪Bellman-Ford Algorithm
▪Shortest Paths in DAG
▪All-Pairs Shortest Paths
▪Lessons Learned
Algorithms for the Real World Lecture 9 Shortest Paths
Algorithms for the Real World Lecture 9
On Directed Acyclic Graphs
What if the graph is a directed acyclic graph (DAG), even with
negative weight ?
Shortest Paths
Use topological order, for a complexity of O(n+m)
Reminder: a topological ordering of a
digraph is a numbering v1, …, vn of the
vertices such that for every edge (vi , vj ),
we have i < j.
MH3400
MH1301MH1201 MH1402 MH2500
MH1200 MH1401 MH1101
MH1100
v2
v1
v3 v4
v5 v6 v7 v8
v9
Algorithms for the Real World Lecture 9
Pseudo-code of Shortest Paths Algorithm for DAG
Shortest Paths
Shortest_Path_DAG(G,s)
D[i] = ∞ for all vertices i #init of D table
D[s] = 0
T = compute_topological_ordering(G)
for i in [0,n-2]: #repeat n-1 times
for all edges (T[i],b;w): #only the edges from T[i]
if D[T[i]] + w < D[b]: D[b] = D[T[i]] + w
return D
Algorithms for the Real World Lecture 9
Example of Shortest Paths Algorithm for DAG
Shortest Paths
Shortest_Path_DAG(G,s)
D[i] = ∞ for all vertices i #init of D table
D[s] = 0
T = compute_topological_ordering(G)
for i in [0,n-2]: #repeat n-1 times
for all edges (T[i],b;w): #only the edges from T[i]
if D[T[i]] + w < D[b]: D[b] = D[T[i]] + w
return D
Initialize D table
D = [S:0, A:∞, B:∞, C:∞, D:∞, E:∞]
A
S
C
B
D
10
10
-6
10
1
E
5
-4
Edges:
(S,A,10)
(S,B,-6)
(A,D,10)
(B,C,1)
(D,B,10)
(D,E,-4)
(E,B,5)
Algorithms for the Real World Lecture 9
Example of Shortest Paths Algorithm for DAG
Shortest Paths
Shortest_Path_DAG(G,s)
D[i] = ∞ for all vertices i #init of D table
D[s] = 0
T = compute_topological_ordering(G)
for i in [0,n-2]: #repeat n-1 times
for all edges (T[i],b;w): #only the edges from T[i]
if D[T[i]] + w < D[b]: D[b] = D[T[i]] + w
return D
A
S
C
B
D
10
10
-6
10
1
E
5
-4
Compute topological order
D = [S:0, A:∞, B:∞, C:∞, D:∞, E:∞]
Edges:
(S,A,10)
(S,B,-6)
(A,D,10)
(B,C,1)
(D,B,10)
(D,E,-4)
(E,B,5)
Topological order: S,A,D,E,B,C
Algorithms for the Real World Lecture 9
Example of Shortest Paths Algorithm for DAG
Shortest Paths
Shortest_Path_DAG(G,s)
D[i] = ∞ for all vertices i #init of D table
D[s] = 0
T = compute_topological_ordering(G)
for i in [0,n-2]: #repeat n-1 times
for all edges (T[i],b;w): #only the edges from T[i]
if D[T[i]] + w < D[b]: D[b] = D[T[i]] + w
return D
A
S
C
B
D
10
10
-6
10
1
E
5
-4
Check for edges starting from S
D = [S:0, A:10, B:-6, C:∞, D:∞, E:∞]
Edges:
(S,A,10)
(S,B,-6)
(A,D,10)
(B,C,1)
(D,B,10)
(D,E,-4)
(E,B,5)
Topological order: S,A,D,E,B,C
Algorithms for the Real World Lecture 9
Example of Shortest Paths Algorithm for DAG
Shortest Paths
Shortest_Path_DAG(G,s)
D[i] = ∞ for all vertices i #init of D table
D[s] = 0
T = compute_topological_ordering(G)
for i in [0,n-2]: #repeat n-1 times
for all edges (T[i],b;w): #only the edges from T[i]
if D[T[i]] + w < D[b]: D[b] = D[T[i]] + w
return D
A
S
C
B
D
10
10
-6
10
1
E
5
-4
Check for edges starting from S
D = [S:0, A:10, B:-6, C:∞, D:20, E:∞]
Edges:
(S,A,10)
(S,B,-6)
(A,D,10)
(B,C,1)
(D,B,10)
(D,E,-4)
(E,B,5)
Topological order: S,A,D,E,B,C
Algorithms for the Real World Lecture 9
Example of Shortest Paths Algorithm for DAG
Shortest Paths
Shortest_Path_DAG(G,s)
D[i] = ∞ for all vertices i #init of D table
D[s] = 0
T = compute_topological_ordering(G)
for i in [0,n-2]: #repeat n-1 times
for all edges (T[i],b;w): #only the edges from T[i]
if D[T[i]] + w < D[b]: D[b] = D[T[i]] + w
return D
S
C
B
D
10
10
-6
10
1
E
5
-4
Check for edges starting from S
D = [S:0, A:10, B:-6, C:∞, D:20, E:16]
Edges:
(S,A,10)
(S,B,-6)
(A,D,10)
(B,C,1)
(D,B,10)
(D,E,-4)
(E,B,5)
Topological order: S,A,D,E,B,C
A
Algorithms for the Real World Lecture 9
Example of Shortest Paths Algorithm for DAG
Shortest Paths
Shortest_Path_DAG(G,s)
D[i] = ∞ for all vertices i #init of D table
D[s] = 0
T = compute_topological_ordering(G)
for i in [0,n-2]: #repeat n-1 times
for all edges (T[i],b;w): #only the edges from T[i]
if D[T[i]] + w < D[b]: D[b] = D[T[i]] + w
return D
S
C
B
10
10
-6
10
1
E
5
-4
Check for edges starting from S
D = [S:0, A:10, B:-6, C:∞, D:20, E:16]
Edges:
(S,A,10)
(S,B,-6)
(A,D,10)
(B,C,1)
(D,B,10)
(D,E,-4)
(E,B,5)
Topological order: S,A,D,E,B,C
A D
Algorithms for the Real World Lecture 9
Example of Shortest Paths Algorithm for DAG
Shortest Paths
Shortest_Path_DAG(G,s)
D[i] = ∞ for all vertices i #init of D table
D[s] = 0
T = compute_topological_ordering(G)
for i in [0,n-2]: #repeat n-1 times
for all edges (T[i],b;w): #only the edges from T[i]
if D[T[i]] + w < D[b]: D[b] = D[T[i]] + w
return D
S
C
B
10
10
-6
10
1
5
-4
Check for edges starting from S
D = [S:0, A:10, B:-6, C:-5, D:20, E:16]
Edges:
(S,A,10)
(S,B,-6)
(A,D,10)
(B,C,1)
(D,B,10)
(D,E,-4)
(E,B,5)
Topological order: S,A,D,E,B,C
A D
E
Algorithms for the Real World Lecture 9
Example of Shortest Paths Algorithm for DAG
Shortest Paths
Shortest_Path_DAG(G,s)
D[i] = ∞ for all vertices i #init of D table
D[s] = 0
T = compute_topological_ordering(G)
for i in [0,n-2]: #repeat n-1 times
for all edges (T[i],b;w): #only the edges from T[i]
if D[T[i]] + w < D[b]: D[b] = D[T[i]] + w
return D
S
C
10
10
-6
10
1
5
-4
n-1 start nodes checked, job finished !
D = [S:0, A:10, B:-6, C:-5, D:20, E:16]
Edges:
(S,A,10)
(S,B,-6)
(A,D,10)
(B,C,1)
(D,B,10)
(D,E,-4)
(E,B,5)
Topological order: S,A,D,E,B,C
A D
EB
Algorithms for the Real World Lecture 9
Correctness of Shortest Paths Algorithm for DAG
Shortest Paths
Lemma: at the end of the Shortest Path algorithm for DAG, the
distance table contains the shortest paths distance from s to all
other nodes u of the graph.
Proof: suppose that vi is the first vertex in the topological ordering such
that D[vi] is not the distance from s to vi. First, note that D[vi] < +∞ since
the algorithm outputs +∞ only if the corresponding node is unreachable
(in which case D[vi] distance would be valid).
Let vk be the penultimate vertex on a shortest path from s to vi. Since
the vertices are numbered according to a topological ordering, we have
that k < i. Thus, D[vk] is correct (we may possibly have vk = s). But
when vk is processed, we relax each outgoing edge from vk, including
the edge on the shortest path from vk to vi. Thus, D[vi] is assigned the
distance from s to vi. But this contradicts the definition of vi; hence, no
such vertex vi can exist.
Algorithms for the Real World Lecture 9
Complexity of Shortest Paths for DAG
Shortest Paths
Shortest_Path_DAG(G,s)
D[i] = ∞ for all vertices i
D[s] = 0
T = compute_topological_ordering(G)
for i in [0,n-2]:
for all edges (T[i],b;w):
if D[T[i]] + w < D[b]: D[b] = D[T[i]] + w
return D
The complexity of the shortest paths algorithm for DAG is O(m+n)
Algorithms for the Real World Lecture 9
Complexity of Shortest Paths for DAG
Shortest Paths
Shortest_Path_DAG(G,s)
D[i] = ∞ for all vertices i
D[s] = 0
T = compute_topological_ordering(G)
for i in [0,n-2]:
for all edges (T[i],b;w):
if D[T[i]] + w < D[b]: D[b] = D[T[i]] + w
return D
The complexity of the shortest paths algorithm for DAG is O(m+n)
O(n)
O(m+n)
O(m)
Complexity = O(n) + O(m+n) + O(m) = O(m+n)
MH 3400 - Algorithms for the Real World
Shortest Paths
Outline
▪Single-Source Shortest Paths
▪Dijkstra’s Algorithm
▪Bellman-Ford Algorithm
▪Shortest Paths in DAG
▪All-Pairs Shortest Paths
▪Lessons Learned
Algorithms for the Real World Lecture 9 Shortest Paths
Algorithms for the Real World Lecture 9
The All-Pairs Shortest Paths Problem
Shortest Paths
All-Pairs Shortest Paths Problem: given a graph G, find the distance
(shortest path) from all nodes to all nodes in G.
Application of computing the shortest path between all pairs of
vertices in a given graph:
Suppose you want to find the “center” vertex in a graph (the one that
minimizes the longest or average distance to all the other nodes). This
might be the best place to start a new business.
Algorithms for the Real World Lecture 9
The All-Pairs Shortest Paths Problem
Of course, we can simply apply the previous methods and repeat them
for all nodes as starting point.
Shortest Paths
If no negative weights, then Dijkstra applied n times leads to a complexity of
O(n3) or O(n(n+m) log(n)) … thus O(n3) or O(n3 log(n)) in the worst case
(for a simple graph mIf negative weights, then Bellman-Ford applied n times leads to a complexity
of O(n2m) … thus O(n4) in the worst case (for a simple graph mOur goal: propose a O(n3) algorithm even when we possibly have
negative weights (yet, no negative cycle)
Algorithms for the Real World Lecture 9
A Dynamic Programming Approach
Floyd-Warshall is a dynamic programming algorithm solving the All-
Pairs Shortest Paths Problem (using the adjacency matrix data structure)
Shortest Paths
Problem division: we randomly number the vertices in the graph
{v0, v1, …, vn-1}. Let Di,j
k to denote the distance from vi to vj using only
intermediate vertices in the set {v0, v1, … , vk-1}.
Initialization: we have:
0 if i=j
Di,j
0 = w((vi, vj)) if (vi, vj) is an edge
+∞ otherwise
Recursion formula: Di,j
k+1 = min { Di,j
k , Di,
k + Dk,j
k }
Algorithms for the Real World Lecture 9
A Dynamic Programming Approach
Floyd-Warshall is a dynamic programming algorithm solving the All-
Pairs Shortest Paths Problem (using the adjacency matrix data structure)
Shortest Paths
Problem division: we randomly number the vertices in the graph
{v0, v1, …, vn-1}. Let Di,j
k to denote the distance from vi to vj using only
intermediate vertices in the set {v0, v1, … , vk-1}.
Initialization: we have:
0 if i=j
Di,j
0 = w((vi, vj)) if (vi, vj) is an edge
+∞ otherwise
Recursion formula: Di,j
k+1 = min { Di,j
k , Di,
k + Dk,j
k }
Going from k to k+1, either we don’t
use node k in the path from i to j
(then path length is Di,j
k ), either we
use node k and then the path length
is Di,
k + Dk,j
k
Algorithms for the Real World Lecture 9
Pseudo-code of Floyd-Warshall’s Algorithm
Shortest Paths
All_Pairs_Shortest_Path_Floyd_Warshall(G)
Let {v
0
,v
1
,…,v
n-1
} an arbitrary numbering of the nodes of G
for i in [0,n-1]:
for j in [0,n-1]:
if i==j: D[0,i,i] = 0
elif (v
i
,v
j
) is an edge: D[0,i,j] = w((v
i
,v
j
))
else: D[0,i,j] = +∞
for k in [0,n-1]:
for i in [0,n-1]:
for j in [0,n-1]:
D[k+1,i,j] = min{D[k,i,j], D[k,i,k] + D[k,k,j]}
return D[n,:,:]
Algorithms for the Real World Lecture 9
Complexity of Floyd-Warshall’s Algorithm
Shortest Paths
All_Pairs_Shortest_Path_Floyd_Warshall(G)
Let {v
0
,v
1
,…,v
n-1
} an arbitrary numbering of the nodes of G
for i in [0,n-1]:
for j in [0,n-1]:
if i==j: D[0,i,i] = 0
elif (v
i
,v
j
) is an edge: D[0,i,j] = w((v
i
,v
j
))
else: D[0,i,j] = +∞
for k in [0,n-1]:
for i in [0,n-1]:
for j in [0,n-1]:
D[k+1,i,j] = min{D[k,i,j], D[k,i,k] + D[k,k,j]}
return D[n,:,:]
O(n2)
If adjacency
matrix
O(n3)
Complexity = O(n2) + O(n3) = O(n3)
Algorithms for the Real World Lecture 9
Implementation of Floyd-Warshall’s Algorithm
Shortest Paths
If we have an adjacency list, the initialisation phase of table D needs
to be tweaked in order to make it O(n2) complexity (naïve is O(n2m))
During the lab session
MH 3400 - Algorithms for the Real World
Shortest Paths
Outline
▪Single-Source Shortest Paths
▪Dijkstra’s Algorithm
▪Bellman-Ford Algorithm
▪Shortest Paths in DAG
▪All-Pairs Shortest Paths
▪Lessons Learned
Algorithms for the Real World Lecture 9 Shortest Paths
Lessons learned
You must be able to:
• Compute efficiently the shortest paths between
nodes in a graph
• Decide what is the most appropriate algorithm
to use in order to compute the shortest paths,
depending on the type of graph.
Algorithms for the Real World Lecture 9 Shortest Paths