MTH00050 – Combinatorial Mathematics

Lecture 8: (Shortest) Path problems

Lecturer: Bùi Văn Thạch

Lab instructors: Nguyễn Ngọc Toàn, Trần Thị Thảo Nhi, Lê Đức Khoan
{bvthach,nntoan,tttnhi,ldkhoan}@[Link]

1
 (Tentative) Schedule 2026
No. Date Location Topic No. Date Location Topic

13/01 C24
6 10/03 C24
1 Introduction, Sets, Proofs Graphs (Part I)
C24/E302 13/03 C24/E302
16/01
7 17/03 C24
20/01 C24 Graphs (Part II)
2 20/03 C24/E302
23/01 C24/E302 General counting methods
8 24/03 C24 Tree problems
27/01 C24 Inclusion-exclusion 27/03 C24/E302
3
30/01 C24/E302
principle 9 31/03 C24 Path problems
03/04 C24/E302
03/02 C24
4 Recurrence relations C24
06/02 C24/E302 10 07/04 Network flows (Part I)
10/04 C24/E302
03/03 C24
5 Generating functions C24
06/03 C24/E302 11 14/04 Network flows (Part II)
17/04 C24/E302
Mid-term test
Final exam

2
Course topics
0. Introduction 6. Graphs

1. Set and counting 7. Tree problems

2. General counting methods for 8. Path problems

arrangements and selections 9. Network flows
3. Inclusion-exclusion principle

4. Recurrence relations

5. Generating functions

3
Goals
1. Identify when and why shortest path algorithms are used (e.g., routing, maps,
networking).

2. Compare and contrast algorithms based on graph types, weights, and constraints.

3. Build algorithmic thinking and problem-solving skills through step-by-step tracing and
implementation.

4. Prepare students to use or implement these algorithms in real-world and academic

settings.

5. Understand deeper concepts like greedy vs dynamic programming strategies.

4
Problem
• We plan to visit
Cần Giờ for food,
sea, and
sightseeing.
• We are at Thủ Đức.
How to find the
shortest path to
reach Cần Giờ?

• Route: Thủ Đức – Q.2 –

Q.1 – Q.4 – Q.7 – Nhà
Bè - Cần Giờ
• Total distance: 48.8km
5
Outline
1. BFS algorithm

2. Dijkstra’s algorithm

3. Bellman–Ford Algorithm

4. Floyd–Warshall algorithm

6
Comparison
Bellman–Ford Floyd–Warshall
Feature / Algorithm BFS Dijkstra’s Algorithm
Algorithm Algorithm
Shortest Path Type Single-source Single-source Single-source All-pairs
Weighted (including Weighted (including
Graph Type Unweighted Weighted (non-negative)
negative) negative)
Sparse graphs with non- Graphs with negative Dense graphs or need
Best Use Case Unweighted graphs
negative weights weights all-pairs shortest paths
Handles Negative
No No Yes Yes
Weights
Handles Negative
No No Detects Detects
Cycles
Time Complexity 𝑂 𝑉 + 𝐸 O((V + E) log V) with heap O(VE) O(V³)
Space Complexity O(V) O(V) O(V) O(V²)
Implementation
Very easy Moderate Simple Moderate/Complex
Simplicity
7
Outline
1. BFS algorithm

2. Dijkstra’s algorithm

3. Bellman–Ford Algorithm

4. Floyd–Warshall algorithm

8
 Breadth-first search (BFS)

Konrad Zuse Edward Forrest Moore

(1910-1995) (1925-2003)
[Link] [Link]

• Breadth-first search (BFS) was first invented by Zuse in 1945 [1] in his rejected PhD thesis and
later reinvented by E.F. Moore in 1959 [2].

• Core Idea: The “Expanding Wavefront”

– BFS begins at a start_node and explores all of its immediate neighbors (nodes at distance 1).

– Then, it explores all unvisited neighbors of those nodes (nodes at distance 2).

– This process continues until all reachable nodes have been visited.

– This level-by-level approach ensures that the path discovered is the shortest in terms of the number of edges.

1. Zuse, Konrad. Der Plankalkül. (1972).

2. Moore, Edward F. The shortest path through a maze. Proc. of the Int. Symp. the Theory of Switching. Harvard Univ. Press, 1959. 9
Pseudocode for BFS
1. BFS_ShortestPath(G, s): //G is the graph, s is the start node to save the
2. for each node u in G: shortest distance
3. c[u] ← ∞ // Distance is initially infinite
4. pred[u] ← NULL // No predecessor yet

5. c[s] ← 0
6. Q ← new Queue()
7. [Link](s)
the predecessor node
(for path reconstruction)
8. while Q is not empty:
9. u ← [Link]()
10. for each neighbor v of u:
11. // If v has not been visited (c is still infinity)
12. if c[v] == ∞:
13. c[v] ← c[u] + 1 // Set distance
14. pred[v] ← u // Set predecessor
15. [Link](v) // Add v to the queue
Example

Given a connected undirected graph G and a root vertex A, find for each vertex X, a shortest path P(X) from A.

E G I

A D
H J

B C
11
 Example (1/5)
A B C D E F G H I J
𝑄= 𝐴
0 ∞, − ∞, − ∞, − ∞, − ∞, − ∞, − ∞, − ∞, − ∞, −

previous vertex that the shortest 𝑣=𝐴 ∞

distance F
path to u must go through

1. BFS_ShortestPath(G, s): ∞ ∞ ∞
2. for each node v in G:
3. c[v] ← ∞ E G I
4. pred[v] ← NULL

5. c[s] ← 0
6. Q ← new Queue() 0 A D ∞
7. [Link](s)
H J
∞ ∞
∞ B C ∞
12
 Example (2/5)
A B C D E F G H I J 𝑣=𝐴
0 1, 𝐴 1, 𝐴 1, 𝐴 1, 𝐴 ∞, − ∞, − ∞, − ∞, − ∞, − 𝑄 = 𝐵, 𝐶, 𝐷, 𝐸

𝑣=𝐴 ∞
Nodes at distance 1
F
8. while Q is not empty: 1 ∞ ∞
9. u ← [Link]()
10. for each neighbor u of v: E G I
11. if c[u] == ∞:
12. c[u] ← c[v] + 1
13. pred[u] ← v
14. [Link](u) 0 A D 1
H J
∞ ∞
1 B C 1
13
 Example (2/5)
A B C D E F G H I J 𝑣=𝐴
0 1, 𝐴 1, 𝐴 1, 𝐴 1, 𝐴 ∞, − ∞, − ∞, − ∞, − ∞, − 𝑄 = 𝐵, 𝐶, 𝐷, 𝐸

𝑣=𝐴 ∞
Nodes at distance 1
F
8. while Q is not empty: ∞ ∞ ∞
9. u ← [Link]()
10. for each neighbor u of v: 𝑢=𝐵 E G I
11. if c[u] == ∞:
12. c[u] ← c[v] + 1
13. pred[u] ← v
14. [Link](u) 0 A D ∞
H J
∞ ∞
1 B C ∞
14
 Example (2/5)
A B C D E F G H I J 𝑣=𝐴
0 1, 𝐴 1, 𝐴 1, 𝐴 1, 𝐴 ∞, − ∞, − ∞, − ∞, − ∞, − 𝑄 = 𝐵, 𝐶, 𝐷, 𝐸

𝑣=𝐴 ∞
Nodes at distance 1
F
8. while Q is not empty: ∞ ∞ ∞
9. u ← [Link]()
10. for each neighbor u of v: 𝑢=𝐶 E G I
11. if c[u] == ∞:
12. c[u] ← c[v] + 1
13. pred[u] ← v
14. [Link](u) 0 A D ∞
H J
∞ ∞
1 B C 1
15
 Example (3/5)
𝑢=𝐵 𝑄= 𝐶, 𝐷, 𝐸
A B C D E F G H I J
𝑢=𝐶 𝑄= 𝐷, 𝐸
0 1, 𝐴 1, 𝐴 1, 𝐴 1, 𝐴 2, 𝐸 2, 𝐷 2, 𝐷 ∞, − ∞, − 𝑢=𝐷 𝑄= 𝐸, 𝐺, 𝐻
2 𝑢=𝐸 𝑄= 𝐺, 𝐻, 𝐹
𝑣=𝐴
Nodes at distance 2
F
8. while Q is not empty: 1 2 ∞
9. u ← [Link]()
10. for each neighbor v of u: E G I
11. if c[v] == ∞:
12. c[v] ← c[u] + 1
13. pred[v] ← u
14. [Link](v) 0 A D 1
H J
2 ∞
1 B C 1
16
 Example (4/5)
A B C D E F G H I J 𝑢=𝐺 𝑄 = 𝐻, 𝐹, 𝐼
0 1, 𝐴 1, 𝐴 1, 𝐴 1, 𝐴 2, 𝐸 2, 𝐷 2, 𝐷 3, 𝐺 3, 𝐻 𝑢=𝐻 𝑄 = 𝐹, 𝐼, 𝐽
𝑢=𝐹 𝑄 = 𝐼, 𝐽
𝑣=𝐴 2
Nodes at distance 3
F
8. while Q is not empty: 1 2 3
9. u ← [Link]()
10. for each neighbor v of u: E G I
11. if c[v] == ∞:
12. c[v] ← c[u] + 1
13. pred[v] ← u
14. [Link](v) 0 A D 1
H J
2 3
1 B C 1
17
 Example (5/5)
A B C D E F G H I J 𝑢=𝐼 𝑄= 𝐽
0 1, 𝐴 1, 𝐴 1, 𝐴 1, 𝐴 2, 𝐸 2, 𝐷 2, 𝐷 3, 𝐺 3, 𝐻 𝑢=𝐽 𝑄= ∅

𝑣=𝐴 2
F
8. while Q is not empty: 1 2 3
9. u ← [Link]()
10. for each neighbor v of u: E G I
11. if c[v] == ∞:
12. c[v] ← c[u] + 1
13. pred[v] ← u
14. [Link](v) 0 A D 1
H J
c[J] = 3 2 3
P(J): A → D → H → J
1 B C 1
18
Complexity
1. BFS_ShortestPath(G, s): //G is the graph, s is the start node
2. for each node u in G: 𝑂 𝑉
3. c[u] ← ∞ // Distance is initially infinite
4. pred[u] ← NULL // No predecessor yet

5. c[s] ← 0
𝑂 1
6. Q ← new Queue()
7. [Link](s)

8. while Q is not empty: 𝑂 𝑉 + |𝐸|

9. u ← [Link]()
10. for each neighbor v of u:
11. // If v has not been visited (dist is still infinity) Total cost:
12. if c[v] == ∞:
13. c[v] ← c[u] + 1 // Set distance 𝑂(|𝑉| + |𝐸|)
14. pred[v] ← u // Set predecessor
15. [Link](v) // Add v to the queue
Correctness

20
Outline
1. BFS algorithm

2. Dijkstra’s algorithm

3. Bellman–Ford Algorithm

4. Floyd–Warshall algorithm

21
 History

Edsger Wybe Dijkstra

(1930–2002)
[Link]/award_winners/dijkstra_1053701.cfm

• The goal of the algorithm is to find the shortest paths between nodes in a non-negative weighted graph.
• It was developed in 1956 by the Dutch scientist Edsger W. Dijkstra [1].
• He received a Turing award in 1972.
– “For fundamental contributions to programming as a high, intellectual challenge; for eloquent insistence and practical demonstration
that programs should be composed correctly, not just debugged into correctness; for illuminating perception of problems at the
foundations of program design.”

[1] Dijkstra, Edsger W. "A note on two problems in connexion with graphs." Edsger Wybe Dijkstra: his life, work, and legacy. 2022. 287-290.
22
Idea
• Like Prim’s algorithm, it greedily grows a tree 𝑇 one vertex and edge at a time,
beginning at the source 𝑎.

• List the vertices in ascending order of their distances from the source.

• Build the shortest-path tree incrementally: at each iteration, add a single edge
that establishes the newly discovered shortest path to the current vertex being
incorporated.

23
Dijkstra’s Algorithm (1/2): initialization

Shortest The rest of

path tree T the vertices

Fringe vertices F
• Initially, the cost from the starting vertex a to vertex u is set to be infinity, i.e., 𝑐 𝑢 = ∞.
• The costs are continuously updated until they represent the actual minimum cost paths from the starting vertex 𝑎 to each
vertex 𝑢.
– We build the shortest path tree 𝑇 starting from vertex 𝑎 and expanding outward.
• At every step, only those vertices connected to at least one vertex already in 𝑇 are eligible to be added next. These are
referred to as the fringe vertices.
• Thus, the graph 𝐺 can be conceptually divided into three regions:
1. The tree T currently under construction,
2. The fringe vertices adjacent to T, and
3. The remaining vertices not yet connected.
24
Dijkstra’s Algorithm (2/2): The Inductive Step
If 𝑐 𝑣 + 𝑤 𝑣, 𝑢 < 𝑐(𝑢),
Shortest The rest of then the value of 𝑐 𝑢
𝑣 𝑢
path tree T the vertices is changed to 𝑐 𝑣
+ 𝑤 𝑣, 𝑢 .
Fringe vertices F

• The one that is chosen is the one for which the length of the shortest cost path
to it from a through T is a minimum among all the vertices in the fringe.

• After each addition of a vertex v to T, each fringe vertex u adjacent to v is

examined and two numbers are compared: the current value of 𝑐 𝑢 and the
value of 𝑐 𝑣 + 𝑤 𝑣, 𝑢 , where 𝑐 𝑣 is the length of the shortest path to v (in T)
and 𝑤 𝑣, 𝑢 is the weight of the edge joining v and u.
25
Algorithm
1. DIJKSTRA(G, s, t): 6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹
2. 𝑇 ≔ ({𝑠}, ∅) ▸ tree starts with the source only
7. V(T) := V(T) ∪ {x}
3. for each vertex u in V − {s}, set c 𝑢 ≔ ∞
8. E(T) := E(T) ∪ { {previous(x), x} }▸ add the chosen
4. 𝑐 𝑠 := 0
edge
5. 𝑣≔𝑠 ▸ most recently added vertex
9. v := x ▸ x becomes the new “current” vertex
6. 𝐹≔ 𝑠 ▸ fringe initially contains the source

8. return c(t) ▸ length of shortest s→t path

7. while 𝑡 ∉ 𝑉 𝑇 :▸ repeat until destination is in the tree

1. 𝐹 ≔ ∪𝑘∈𝑉 𝑇 Adj 𝑘 ∖𝑉 𝑇 adjacent vertices of V(T) except

2. for each u in Adj(v) \ V(T): those in V(T)
3. if c(v) + w(v, u) < c(u): ▸find a better cost
4. c(u) := c(v) + w(v, u) ▸update the cost only UPDATE the cost of the vertices
5. previous(u) := v ▸ keep track of shortest path to u adjacent to v but not in V(T)
26
Example (1/68)
Given a connected undirected graph G with non-negative weights on the edges and a root vertex A, find for
each vertex X, a directed path P(X) from A to X so that the sum of the weights on the edges in P(X) is as small
as possible.
F
14
9
8
9
E G I
10
6 7
9
1 11 7
A D
12
2
5
4
H 6
J

B 3
C
27
 Example (2/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴
0 ∞, − ∞, − ∞, − ∞, − ∞, − ∞, − ∞, − ∞, − ∞, −
𝐹= 𝐴
𝐸 𝑇 =∅
previous vertex that the shortest 𝑣=𝐴 ∞
cost F
path to u must go through
14
9
1. 𝑇 ≔ ({𝑠}, ∅) ▸ tree starts with the source only ∞ 8 ∞ ∞
9
2. 𝑐 𝑠 := 0 E G I
10
3. for each vertex u in V − {s}: 6 7
9
4. c 𝑢 ≔∞ ▸ initialise zero cost 1 11 7
5. 𝑣≔𝑠 ▸ most recently added vertex
0 A D ∞
12
6. 𝐹≔ 𝑠 ▸ fringe initially contains the source
2
5
4
H 6
J
∞ ∞
∞ B 3
C ∞
28
 Example (3/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴
0, 𝐴 ∞, − ∞, − ∞, − ∞, − ∞, − ∞, − ∞, − ∞, − ∞, −
𝐹 = 𝐵, 𝐶, 𝐷, 𝐸
𝐸 𝑇 =∅
𝑣=𝐴 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
∞ 8 ∞ ∞
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u): ▸find a better cost E G I
10
4. c(u) := c(v) + w(v, u) ▸update the cost 6 7
9
5. previous(u) := v ▸ keep track of shortest path to u 1 11 7
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label 0 A D ∞
𝑝∈𝐹
12
7. V(T) := V(T) ∪ {x}
2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge ∞
9. v := x ▸ x becomes the new “current” vertex
∞
∞ B 3
C ∞
29
Example (4/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴
0, 𝐴 2, 𝐴 ∞, − ∞, − ∞, − ∞, − ∞, − ∞, − ∞, − ∞, −
𝐹 = 𝐵, 𝐶, 𝐷, 𝐸
𝐸 𝑇 =∅
𝑣=𝐴 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 Adj 𝑣 \V 𝑇 = 𝐵, 𝐶, 𝐷, 𝐸 9
𝑇
∞ 8 ∞ ∞
2. for each u in Adj(v) \ V(T): 𝑢 = 𝐵 9
3. if c(v) + w(v, u) < c(u): 𝑐 𝐴 + 𝑤 𝐵, 𝐴 = 2 < ∞ = 𝑐 𝐵
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 𝑐 𝐵 = 2 9
5. previous(u) := v 1 11 7
0 A D ∞
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge ∞ ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C ∞
30
Example (5/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴
0, 𝐴 2, 𝐴 5, 𝐴 ∞, − ∞, − ∞, − ∞, − ∞, − ∞, − ∞, −
𝐹 = 𝐵, 𝐶, 𝐷, 𝐸
𝐸 𝑇 =∅
𝑣=𝐴 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 Adj 𝑣 \V 𝑇 = 𝐵, 𝐶, 𝐷, 𝐸 9
𝑇
∞ 8 ∞ ∞
2. for each u in Adj(v) \ V(T): 𝑢 = 𝐶 9
3. if c(v) + w(v, u) < c(u): 𝑐 𝐴 + 𝑤 𝐶, 𝐴 = 5 < ∞ = 𝑐 𝐶
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 𝑐 𝐶 = 5 9
5. previous(u) := v 1 11 7
0 A D ∞
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge ∞ ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
31
Example (6/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 ∞, − ∞, − ∞, − ∞, − ∞, − ∞, −
𝐹 = 𝐵, 𝐶, 𝐷, 𝐸
𝐸 𝑇 =∅
𝑣=𝐴 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 Adj 𝑣 \V 𝑇 = 𝐵, 𝐶, 𝐷, 𝐸 9
𝑇
∞ 8 ∞ ∞
2. for each u in Adj(v) \ V(T): 𝑢 = 𝐷 9
3. if c(v) + w(v, u) < c(u): 𝑐 𝐴 + 𝑤 𝐷, 𝐴 = 1 < ∞ = 𝑐 𝐷
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 𝑐 𝐷 = 1 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge ∞ ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
32
Example (7/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − ∞, − ∞, − ∞, − ∞, −
𝐹 = 𝐵, 𝐶, 𝐷, 𝐸
𝐸 𝑇 =∅
𝑣=𝐴 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 Adj 𝑣 \V 𝑇 = 𝐵, 𝐶, 𝐷, 𝐸 9
𝑇
6 8 ∞ ∞
2. for each u in Adj(v) \ V(T): 𝑢 = 𝐸 9
3. if c(v) + w(v, u) < c(u): 𝑐 𝐴 + 𝑤 𝐸, 𝐴 = 6 < ∞ = 𝑐 𝐸
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 𝑐 𝐸 = 6 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge ∞ ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
33
Example (8/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − ∞, − ∞, − ∞, − ∞, −
𝐹 = 𝐵, 𝐶, 𝐷, 𝐸
𝐸 𝑇 =∅
𝑣=𝐴 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 ∞ ∞
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 𝑥 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge ∞ ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C ∞
34
Example (9/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − ∞, − ∞, − ∞, − ∞, −
𝐹 = 𝐵, 𝐶, 𝐷, 𝐸
𝐸 𝑇 =∅
𝑣=𝐴 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 ∞ ∞
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge ∞ ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C ∞
35
Example (10/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − ∞, − ∞, − ∞, − ∞, −
𝐹 = 𝐵, 𝐶, 𝐷, 𝐸
𝐸 𝑇 = 𝐴, 𝐷
𝑣=𝐴 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 ∞ ∞
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge ∞ ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C ∞
36
Example (11/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − ∞, − ∞, − ∞, − ∞, −
𝐹 = 𝐵, 𝐶, 𝐷, 𝐸
𝐸 𝑇 = 𝐴, 𝐷
𝑣=𝐷 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 ∞ ∞
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge ∞ ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C ∞
37
Example (12/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − ∞, − ∞, − ∞, − ∞, −
𝐹 = 𝐵, 𝐶, 𝐻, 𝐺, 𝐸
𝐸 𝑇 = 𝐴, 𝐷
𝑣=𝐷 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 Adj 𝑣 \V 𝑇 = 𝐶, 𝐻, 𝐺, 𝐸 9
𝑇
6 8 ∞ ∞
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge ∞ ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
38
Example (13/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − ∞, − ∞, − ∞, − ∞, −
𝐹 = 𝐵, 𝐶, 𝐻, 𝐺, 𝐸
𝐸 𝑇 = 𝐴, 𝐷
𝑣=𝐷 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 Adj 𝑣 \V 𝑇 = 𝐶, 𝐻, 𝐺, 𝐸 9
𝑇
6 8 ∞ ∞
2. for each u in Adj(v) \ V(T): 𝑢 = 𝐶 9
3. if c(v) + w(v, u) < c(u): 𝑐 𝐷 + 𝑤 𝐶, 𝐷 = 5 = 𝑐 𝐶
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge ∞ ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
39
Example (14/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − ∞, − 13, D ∞, − ∞, −
𝐹 = 𝐵, 𝐶, 𝐻, 𝐺, 𝐸
𝐸 𝑇 = 𝐴, 𝐷
𝑣=𝐷 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 Adj 𝑣 \V 𝑇 = 𝐶, 𝐻, 𝐺, 𝐸 9
𝑇
6 8 ∞ ∞
2. for each u in Adj(v) \ V(T): 𝑢 = 𝐻 9
3. if c(v) + w(v, u) < c(u): 𝑐 𝐷 + 𝑤 𝐻, 𝐷 = 13 < ∞ = 𝑐 𝐻
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 𝑐 𝐻 =13 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
40
Example (15/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − 8, D 13, 𝐷 ∞, − ∞, −
𝐹 = 𝐵, 𝐶, 𝐻, 𝐺, 𝐸
𝐸 𝑇 = 𝐴, 𝐷
𝑣=𝐷 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 Adj 𝑣 \V 𝑇 = 𝐶, 𝐻, 𝐺, 𝐸 9
𝑇
6 8 8 ∞
2. for each u in Adj(v) \ V(T): 𝑢 = 𝐺 9
3. if c(v) + w(v, u) < c(u): 𝑐 𝐷 + 𝑤 𝐺, 𝐷 = 8 < ∞ = 𝑐 𝐺
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 𝑐 𝐺 = 8 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
41
Example (16/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − 8, D 13, 𝐷 ∞, − ∞, −
𝐹 = 𝐵, 𝐶, 𝐻, 𝐺, 𝐸
𝐸 𝑇 = 𝐴, 𝐷
𝑣=𝐷 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 Adj 𝑣 \V 𝑇 = 𝐶, 𝐻, 𝐺, 𝐸 9
𝑇
6 8 8 ∞
2. for each u in Adj(v) \ V(T): 𝑢 = 𝐸 9
3. if c(v) + w(v, u) < c(u): 𝑐 𝐷 + 𝑤 𝐸, 𝐷 = 11 > 𝑐 𝐸
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
42
Example (17/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − 8, D 13, 𝐷 ∞, − ∞, −
𝐹 = 𝐵, 𝐶, 𝐻, 𝐺, 𝐸
𝐸 𝑇 = 𝐴, 𝐷
𝑣=𝐷 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 ∞
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 𝑥 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
43
Example (18/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − 8, D 13, 𝐷 ∞, − ∞, −
𝐹 = 𝐵, 𝐶, 𝐻, 𝐺, 𝐸
𝐸 𝑇 = 𝐴, 𝐷
𝑣=𝐷 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 ∞
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 𝑥 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
44
Example (19/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − 8, D 13, 𝐷 ∞, − ∞, −
𝐹 = 𝐵, 𝐶, 𝐻, 𝐺, 𝐸
𝐸 𝑇 = 𝐴, 𝐷 , 𝐴, 𝐵
𝑣=𝐷 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 ∞
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 𝑥 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
45
Example (20/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − 8, D 13, 𝐷 ∞, − ∞, −
𝐹 = 𝐵, 𝐶, 𝐻, 𝐺, 𝐸
𝐸 𝑇 = 𝐴, 𝐷 , 𝐴, 𝐵
𝑣=𝐵 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 ∞
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
46
Example (21/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − 8, D 13, 𝐷 ∞, − ∞, −
𝐹 = 𝐶, 𝐻, 𝐺, 𝐸
𝐸 𝑇 = 𝐴, 𝐷 , 𝐴, 𝐵
𝑣=𝐵 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 ∞
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
47
Example (22/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − 8, D 13, 𝐷 ∞, − ∞, −
𝐹 = 𝐶, 𝐻, 𝐺, 𝐸
𝐸 𝑇 = 𝐴, 𝐷 , 𝐴, 𝐵
𝑣=𝐵 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 Adj 𝑣 \V 𝑇 = 𝐶 9
𝑇
6 8 8 ∞
2. for each u in Adj(v) \ V(T): 𝑢 = 𝐶 9
3. if c(v) + w(v, u) < c(u): 𝑐 𝐵 + 𝑤 𝐶, 𝐵 = 5 = 𝑐 5
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
48
Example (23/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − 8, D 13, 𝐷 ∞, − ∞, −
𝐹 = 𝐶, 𝐻, 𝐺, 𝐸
𝐸 𝑇 = 𝐴, 𝐷 , 𝐴, 𝐵
𝑣=𝐵 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 ∞
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 𝑥 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
49
Example (24/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − 8, D 13, 𝐷 ∞, − ∞, −
𝐹 = 𝐶, 𝐻, 𝐺, 𝐸
𝐸 𝑇 = 𝐴, 𝐷 , 𝐴, 𝐵
𝑣=𝐵 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 ∞
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 𝑥 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
50
Example (25/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − 8, D 13, 𝐷 ∞, − ∞, −
𝐹 = 𝐶, 𝐻, 𝐺, 𝐸
𝐸 𝑇 = 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶
𝑣=𝐵 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 ∞
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 𝑥 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
51
Example (26/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − 8, D 13, 𝐷 ∞, − ∞, −
𝐹 = 𝐶, 𝐻, 𝐺, 𝐸
𝐸 𝑇 = 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶
𝑣=𝐶 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 ∞
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
52
Example (27/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − 8, D 13, 𝐷 ∞, − ∞, −
𝐹 = 𝐻, 𝐺, 𝐸
𝐸 𝑇 = 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶
𝑣=𝐶 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 ∞
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
53
Example (28/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − 8, D 13, 𝐷 ∞, − ∞, −
𝐹 = 𝐻, 𝐺, 𝐸
𝐸 𝑇 = 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶
𝑣=𝐶 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 Adj 𝑣 \V 𝑇 = ∅ 9
𝑇
6 8 8 ∞
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
54
Example (29/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − 8, D 13, 𝐷 ∞, − ∞, −
𝐹 = 𝐻, 𝐺, 𝐸
𝐸 𝑇 = 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶
𝑣=𝐶 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 ∞
2. for each u in Adj(v) \ V(T): 𝑥 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
55
Example (30/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − 8, D 13, 𝐷 ∞, − ∞, −
𝐹 = 𝐻, 𝐺, 𝐸
𝐸 𝑇 = 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶
𝑣=𝐶 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 ∞
2. for each u in Adj(v) \ V(T): 𝑥 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
56
Example (31/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − 8, D 13, 𝐷 ∞, − ∞, −
𝐹 = 𝐻, 𝐺, 𝐸
𝐸 𝑇 = 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐶 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 ∞
2. for each u in Adj(v) \ V(T): 𝑥 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
57
Example (32/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − 8, D 13, 𝐷 ∞, − ∞, −
𝐹 = 𝐻, 𝐺, 𝐸
𝐸 𝑇 = 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐸 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 ∞
2. for each u in Adj(v) \ V(T): 𝑣 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
58
Example (33/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − 8, D 13, 𝐷 ∞, − ∞, −
𝐹 = 𝐻, 𝐺, 𝐹
𝐸 𝑇 = 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐸 ∞
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 ∞
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
59
Example (34/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 ∞, − ∞, −
𝐹 = 𝐻, 𝐺, 𝐹
𝐸 𝑇 = 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐸 15
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 Adj 𝑣 \V 𝑇 = 𝐹 9
𝑇
6 8 8 ∞
2. for each u in Adj(v) \ V(T): 𝑢 = 𝐹 9
3. if c(v) + w(v, u) < c(u): 𝑐 𝐸 + 𝑤 𝐹, 𝐸 = 15 < ∞ = 𝑐 𝐹
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 𝑐 𝐹 = 15 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
60
Example (35/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 ∞, − ∞, −
𝐹 = 𝐻, 𝐺, 𝐹
𝐸 𝑇 = 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐸 15
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 𝑥 8 ∞
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
61
Example (36/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 ∞, − ∞, −
𝐹 = 𝐻, 𝐺, 𝐹
𝐸 𝑇 = 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐸 15
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 𝑥 8 ∞
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
62
Example (37/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 ∞, − ∞, −
𝐹 = 𝐻, 𝐺, 𝐹
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐸 15 𝐺, 𝐷 }
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 𝑥 8 ∞
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
63
Example (38/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 ∞, − ∞, −
𝐹 = 𝐻, 𝐺, 𝐹
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐺 15
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 ∞
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
64
Example (39/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 ∞, − ∞, −
𝐹 = 𝐻, 𝐺, 𝐹
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐺 15
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 ∞
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
65
Example (40/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 ∞, − ∞, −
𝐹 = 𝐻, 𝐼, 𝐹
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐺 15 𝐺, 𝐷 }
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 ∞
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
66
Example (41/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 ∞, − ∞, −
𝐹 = 𝐻, 𝐼, 𝐹
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐺 15 𝐺, 𝐷 }
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 Adj 𝑣 \V 𝑇 = 𝐻, 𝐼, 𝐹 9
𝑇
6 8 8 ∞
2. for each u in Adj(v) \ V(T): 𝑢 = 𝐻 9
3. if c(v) + w(v, u) < c(u): 𝑐 𝐺 + 𝑤 𝐻, 𝐺 = 19 > 13 = 𝑐 𝐻
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
67
Example (42/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G ∞, −
𝐹 = 𝐻, 𝐼, 𝐹
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐺 15 𝐺, 𝐷 }
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 Adj 𝑣 \V 𝑇 = 𝐻, 𝐼, 𝐹 9
𝑇
6 8 8 17
2. for each u in Adj(v) \ V(T): 𝑢 = 𝐼 9
3. if c(v) + w(v, u) < c(u): 𝑐 𝐺 + 𝑤 𝐼, 𝐺 = 17 < ∞ = 𝑐 𝐻
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 𝑐 𝐹 = 17 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
68
Example (43/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G ∞, −
𝐹 = 𝐻, 𝐼, 𝐹
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐺 15 𝐺, 𝐷 }
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 Adj 𝑣 \V 𝑇 = 𝐻, 𝐼, 𝐹 9
𝑇
6 8 8 17
2. for each u in Adj(v) \ V(T): 𝑢 = 𝐹 9
3. if c(v) + w(v, u) < c(u): 𝑐 𝐺 + 𝑤 𝐹, 𝐺 = 16 > 15 = 𝑐 𝐹
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
69
Example (44/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G ∞, −
𝐹 = 𝐻, 𝐼, 𝐹
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐺 15 𝐺, 𝐷 }
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 17
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1 𝑥
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
70
Example (45/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺, 𝐻
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G ∞, −
𝐹 = 𝐻, 𝐼, 𝐹
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐺 15 𝐺, 𝐷 }
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 17
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1 𝑥
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
71
Example (46/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺, 𝐻
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G ∞, −
𝐹 = 𝐻, 𝐼, 𝐹
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐺 15 𝐺, 𝐷 , 𝐻, 𝐷 }
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 17
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1 𝑥
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
72
Example (47/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺, 𝐻
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G ∞, −
𝐹 = 𝐻, 𝐼, 𝐹
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐻 15 𝐺, 𝐷 , 𝐻, 𝐷 }
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 17
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
73
Example (48/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺, 𝐻
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G ∞, −
𝐹 = 𝐽, 𝐼, 𝐹
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐻 15 𝐺, 𝐷 , 𝐻, 𝐷 }
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 17
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 ∞
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
74
Example (49/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺, 𝐻
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G 19, H
𝐹 = 𝐽, 𝐼, 𝐹
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐻 15 𝐺, 𝐷 , 𝐻, 𝐷 }
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 Adj 𝑣 \V 𝑇 = 𝐼, 𝐽 9
𝑇
6 8 8 17
2. for each u in Adj(v) \ V(T): 𝑢 = 𝐽 9
3. if c(v) + w(v, u) < c(u): 𝑐 𝐻 + 𝑤 𝐽, 𝐻 = 19 < ∞ = 𝑐 𝐽
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 𝑐 𝐽 = 19 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 19
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
75
Example (50/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺, 𝐻
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G 19, H
𝐹 = 𝐽, 𝐼, 𝐹
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐻 15 𝐺, 𝐷 , 𝐻, 𝐺 }
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 Adj 𝑣 \V 𝑇 = 𝐼, 𝐽 9
𝑇
6 8 8 17
2. for each u in Adj(v) \ V(T): 𝑢 = 𝐼 9
3. if c(v) + w(v, u) < c(u): 𝑐 𝐻 + 𝑤 𝐼, 𝐻 = 22 > 17 = 𝑐 𝐼
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 19
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
76
Example (51/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺, 𝐻
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G 19, H
𝐹 = 𝐽, 𝐼, 𝐹
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐻 𝑥
15 𝐺, 𝐷 , 𝐻, 𝐷 }
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 17
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 19
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
77
Example (52/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺, 𝐻, 𝐹
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G 19, H
𝐹 = 𝐽, 𝐼, 𝐹
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐻 𝑥
15 𝐺, 𝐷 , 𝐻, 𝐷 }
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 17
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 19
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
78
Example (53/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺, 𝐻, 𝐹
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G 19, H
𝐹 = 𝐽, 𝐼, 𝐹
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐻 𝑥
15 𝐺, 𝐷 , 𝐻, 𝐷 , 𝐹, 𝐺 }
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 17
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 19
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
79
Example (54/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺, 𝐻, 𝐹
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G 19, H
𝐹 = 𝐽, 𝐼, 𝐹
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐹 15 𝐺, 𝐷 , 𝐻, 𝐷 , 𝐹, 𝐺 }
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 17
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 19
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
80
Example (55/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺, 𝐻, 𝐹
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G 19, H
𝐹 = 𝐽, 𝐼
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐹 15 𝐺, 𝐷 , 𝐻, 𝐷 , 𝐹, 𝐺 }
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 17
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 19
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
81
Example (56/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺, 𝐻, 𝐹
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G 19, H
𝐹 = 𝐽, 𝐼
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐹 15 𝐺, 𝐷 , 𝐻, 𝐷 , 𝐹, 𝐺 }
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 Adj 𝑣 \V 𝑇 = 𝐼 9
𝑇
6 8 8 17
2. for each u in Adj(v) \ V(T): 𝑢 = 𝐼 9
3. if c(v) + w(v, u) < c(u): 𝑐 𝐹 + 𝑤 𝐼, 𝐹 = 29 > 17 = 𝑐 𝐼
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 19
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
82
Example (57/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺, 𝐻, 𝐹
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G 19, H
𝐹 = 𝐽, 𝐼
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐹 15 𝐺, 𝐷 , 𝐻, 𝐷 , 𝐹, 𝐺 }
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 𝑥 17
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 19
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
83
Example (58/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺, 𝐻, 𝐹, 𝐼
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G 19, H
𝐹 = 𝐽, 𝐼
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐹 15 𝐺, 𝐷 , 𝐻, 𝐷 , 𝐹, 𝐺 }
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 𝑥 17
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 19
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
84
Example (59/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺, 𝐻, 𝐹, 𝐼
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G 19, H
𝐹 = 𝐽, 𝐼
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐹 15 𝐺, 𝐷 , 𝐻, 𝐷 , 𝐹, 𝐺 , 𝐼, 𝐺 }
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 𝑥 17
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 19
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
85
Example (60/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺, 𝐻, 𝐹, 𝐼
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G 19, H
𝐹 = 𝐽, 𝐼
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐼 15 𝐺, 𝐷 , 𝐻, 𝐺 , 𝐹, 𝐺 , 𝐼, 𝐺 }
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 17
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 19
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
86
Example (61/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺, 𝐻, 𝐹, 𝐼
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G 19, H
𝐹= 𝐽
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐼 15 𝐺, 𝐷 , 𝐻, 𝐷 , 𝐹, 𝐺 , 𝐼, 𝐺 }
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 17
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 19
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
87
Example (62/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺, 𝐻, 𝐹, 𝐼
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G 19, H
𝐹= 𝐽
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐼 15 𝐺, 𝐷 , 𝐻, 𝐷 , 𝐹, 𝐺 , 𝐼, 𝐺 }
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 Adj 𝑣 \V 𝑇 = 𝐽 9
𝑇
6 8 8 17
2. for each u in Adj(v) \ V(T): 𝑢 = 𝐽 9
3. if c(v) + w(v, u) < c(u): 𝑐 𝐼 + 𝑤 𝐽, 𝐼 = 24 > 19 = 𝑐 𝐽
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 19
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
88
Example (63/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺, 𝐻, 𝐹, 𝐼
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G 19, H
𝐹= 𝐽
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐼 15 𝐺, 𝐷 , 𝐻, 𝐷 , 𝐹, 𝐺 , 𝐼, 𝐺 }
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 17
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1 𝑥
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 19
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
89
Example (64/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺, 𝐻, 𝐹, 𝐼, 𝐽
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G 19, H
𝐹= 𝐽
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐼 15 𝐺, 𝐷 , 𝐻, 𝐷 , 𝐹, 𝐺 , 𝐼, 𝐺 }
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 17
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1 𝑥
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 19
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
90
Example (65/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺, 𝐻, 𝐹, 𝐼, 𝐽
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G 19, H
𝐹= 𝐽
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐼 15 𝐺, 𝐷 , 𝐻, 𝐷 , 𝐹, 𝐺 , 𝐼, 𝐺 , 𝐽, 𝐻 }
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 17
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1 𝑥
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 19
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
91
Example (66/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺, 𝐻, 𝐹, 𝐼, 𝐽
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G 19, H
𝐹= 𝐽
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
𝑣=𝐽 15 𝐺, 𝐷 , 𝐻, 𝐷 , 𝐹, 𝐺 , 𝐼, 𝐺 , 𝐽, 𝐻 }
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 17
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 19
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
92
Example (67/68)
A B C D E F G H I J 𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺, 𝐻, 𝐹, 𝐼, 𝐽
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸
0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G 19, H
𝐺, 𝐷 , 𝐻, 𝐷 , 𝐹, 𝐺 , 𝐼, 𝐺 , 𝐽, 𝐻 }
15
while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree F
14
1. 𝐹 ≔ ∪𝑘∈𝑉 Adj 𝑘 ∖𝑉 𝑇 9
𝑇
6 8 8 17
2. for each u in Adj(v) \ V(T): 9
3. if c(v) + w(v, u) < c(u):
E G I
10
6 7
4. c(u) := c(v) + w(v, u) 9
5. previous(u) := v 1 11 7
0 A D 1
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label
𝑝∈𝐹 12
7. V(T) := V(T) ∪ {x} 2
5
4
H 6
J
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 13 19
9. v := x ▸ x becomes the new “current” vertex
2 B 3
C 5
93
Example (68/68): Summary
𝑉 𝑇 = 𝐴, 𝐷, 𝐵, 𝐶, 𝐸, 𝐺, 𝐻, 𝐹, 𝐼, 𝐽
𝐸 𝑇 = { 𝐴, 𝐷 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐴, 𝐸 , 𝐺, 𝐷 , 𝐻, 𝐺 , 𝐹, 𝐺 , 𝐼, 𝐺 , 𝐽, 𝐻 }
Step A B C D E F G H I J
0 0, 𝐴 ∞, − ∞, − ∞, − ∞, − ∞, − ∞, − ∞, − ∞, − ∞, −
1 0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − ∞, − ∞, − ∞, − ∞, −
2 0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − 8, D 13, 𝐷 ∞, − ∞, −
3 0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − 8, D 13, 𝐷 ∞, − ∞, −
4 0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 ∞, − 8, D 13, 𝐷 ∞, − ∞, −
5 0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 ∞, − ∞, −
6 0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G ∞, −
7 0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G 19, H
8 0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G 19, H
9 0, 𝐴 2, 𝐴 5, 𝐴 1, 𝐴 6, 𝐴 15, E 8, D 13, 𝐷 17, G 19, H

94
Exercise

95
Solution

96
Complexity

while 𝑡 ∉ 𝑉 𝑇 : ▸ repeat until destination is in the tree 𝑂 𝑉

1. 𝐹 ≔ ∪𝑘∈𝑉 𝑇 Adj 𝑘 ∖𝑉 𝑇 𝑂 𝑉
2. for each u in Adj(v) \ V(T): 𝑂 𝑉
3. if c(v) + w(v, u) < c(u): Total cost:
4.
5.
c(u) := c(v) + w(v, u)
previous(u) := v
𝑂 𝑉2
6. x := argmin 𝑐 𝑝 ▸ fringe vertex with min label 𝑂 𝑉
𝑝∈𝐹
7. V(T) := V(T) ∪ {x} 𝑂 1
8. E(T) := E(T)∪{{previous(x), x} }▸ add the chosen edge 𝑂 1
9. v := x ▸ x becomes the new “current” vertex 𝑂 1
97
Correctness

98
Dijkstra’s Algorithm (2/2): The Inductive Step
If 𝑐 𝑣 + 𝑤 𝑣, 𝑢 < 𝑐(𝑢),
Shortest The rest of then the value of 𝑐 𝑢
𝑣 𝑢
path tree T the vertices is changed to 𝑐 𝑣
+ 𝑤 𝑣, 𝑢 .
Fringe vertices F

• The one that is chosen is the one for which the length of the shortest cost path
to it from a through T is a minimum among all the vertices in the fringe.

• After each addition of a vertex v to T, each fringe vertex u adjacent to v is

examined and two numbers are compared: the current value of 𝑐 𝑢 and the
value of 𝑐 𝑣 + 𝑤 𝑣, 𝑢 , where 𝑐 𝑣 is the length of the shortest path to v (in T)
and 𝑤 𝑣, 𝑢 is the weight of the edge joining v and u.
99
100
Outline
1. BFS algorithm

2. Dijkstra’s algorithm

3. Bellman–Ford Algorithm

4. Floyd–Warshall algorithm

10
1
Dijkstra’s algorithm vs negative weighted graphs (1/2)
• Find the shortest path from A to E by Dijkstra’s algorithm.

A D 5
10
1 -10
E
1

B C

102
Dijkstra’s algorithm vs negative weighted graphs (2/2)
• Find the shortest path from A to E by Dijkstra’s algorithm.

A D 5 A D 5
10 10
1 -10
E 1 -10
E
1 1

B C B C

Right solution:
A→B→D→E. Total cost: 7.
A→C→D→E. Total cost: 5.
103
 History

Richard Ernest Bellman Lester “Les” Randolph Ford, Jr.

(1920–1984) (1927–2017)
[Link]/Biographies/Bellman Published by Santa Barbara News-Press from Mar. 12 to Mar. 16, 2017.

• The goal of the algorithm is to find the shortest paths between nodes in a weighted graph in
which some edges might have negative weights.

• It was developed in 1956 by the American scientist Lester Randolph Ford [2] and in 1958 by
Richard Ernest Bellman [1]
– Bellman received the John von Neumann Theory Prize in 1976.

[1] Bellman, Richard. On a routing problem. Quarterly of applied mathematics 16.1 (1958): 87-90.
[2] Ford Jr, Lester R. Network flow theory. No. P923. 1956. 104
Ideas
• It repeatedly relaxes all edges in the graph to progressively improve the
shortest-path estimates from the source to every vertex.

• A shortest path from the source to any vertex in a graph with 𝑉 vertices can have
at most 𝑉−1 edges (because a simple path can’t repeat vertices).
• If you relax all edges 𝑉−1 times, you guarantee the shortest distances are
found—even if some edges have negative weights.
• A final pass over all edges detects if a further relaxation is possible, which
indicates a negative weight cycle.
105
Bellman-Ford(G, s)

1. for all v ∈ V // Step 1: Initialize distances and predecessors Relax(u, v)

2. dist[v] ← ∞ // Set all distances to infinity (unreachable at start) 1. if dist[u] + w(u, v) < dist[v] // If found a shorter path to v
2. dist[v] ← dist[u] + w(u, v) // Update distance to v
3. prev[v] ← null // No predecessor yet
3. prev[v] ← u // Update predecessor of v
4. dist[s] ← 0 // Distance to source is 0

5. for i ← 1 to |V| − 1 // Step 2: Relax edges |V| - 1 times

6. for each edge (u, v) ∈ E // Loop through all edges

7. Relax(u, v)

8. for each edge (u, v) ∈ E // Step 3: Check for negative-weight cycles

9. if dist[v] > dist[u] + w(u, v) // If still can relax an edge, cycle exists

10. return false // Negative-weight cycle detected

11. return true // No negative cycle, algorithm successful

106
Example (1/9)
• Find the shortest path from A to E by Bellman-Ford algorithm.

A D 5
10
1 -10
E
1
7
B C

107
 Example (2/9)
A B C D E 𝑉 = 𝐴, 𝐵, 𝐶, 𝐷, 𝐸
0, 𝐴 ∞, − ∞, − ∞, − ∞, − 𝐸= 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐵, 𝐷 , 𝐶, 𝐷 , 𝐷, 𝐸 , 𝐸, 𝐶

previous vertex that the shortest

cost
path to 𝑢 must go through 0 ∞
A D 5
1. for all v ∈ V // Step 1: Initialize distances and predecessors 10
2. dist[v] ← ∞ // Set all distances to infinity (unreachable at start) 1 -10
E ∞
3. prev[v] ← null // No predecessor yet 1
4. dist[s] ← 0 // Distance to source is 0 7
B C
∞ ∞

108
 Example (3/9)
A B C D E 𝑉 = 𝐴, 𝐵, 𝐶, 𝐷, 𝐸
0, 𝐴 1, 𝐴 ∞, − ∞, − ∞, − 𝐸= 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐵, 𝐷 , 𝐶, 𝐷 , 𝐷, 𝐸 , 𝐸, 𝐶
𝐴, 𝐵
4 0 ∞
A D 5
1. for i ← 1 to |V| − 1 𝑖=1
// Step 2: Relax edges |V| - 1 times 10
2. for each edge (u, v) ∈ E // Loop through all edges 1 -10
E ∞
3. Relax(u, v) 1
7

Relax(u, v)
B C
1. if dist[A] + w(A, B) = 0 + 1 < ∞ = dist[B] // If found a shorter path to v 1 ∞
2. dist[B] ← dist[A] + w(A, B) // Update distance to v
3. prev[B] ← A // Update predecessor of v

109
 Example (4/9)
A B C D E 𝑉 = 𝐴, 𝐵, 𝐶, 𝐷, 𝐸
0, 𝐴 1, 𝐴 10, 𝐴 ∞, − ∞, − 𝐸= 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐵, 𝐷 , 𝐶, 𝐷 , 𝐷, 𝐸 , 𝐸, 𝐶
𝐴, 𝐶
4 0 ∞
A D 5
1. for i ← 1 to |V| − 1 𝑖=1
// Step 2: Relax edges |V| - 1 times 10
2. for each edge (u, v) ∈ E // Loop through all edges 1 -10
E ∞
3. Relax(u, v) 1
7

Relax(u, v)
B C
1. if dist[A] + w(A, C) = 0 + 10 < ∞ = dist[C] // If found a shorter path to v 1 10
2. dist[C] ← dist[A] + w(A, C) // Update distance to v
3. prev[C] ← A // Update predecessor of v

110
 Example (5/9)
A B C D E 𝑉 = 𝐴, 𝐵, 𝐶, 𝐷, 𝐸
0, 𝐴 1, 𝐴 10, 𝐴 2, 𝐵 ∞, − 𝐸= 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐵, 𝐷 , 𝐶, 𝐷 , 𝐷, 𝐸 , 𝐸, 𝐶
𝐵, 𝐷
4 0 2
A D 5
1. for i ← 1 to |V| − 1 𝑖=1
// Step 2: Relax edges |V| - 1 times 10
2. for each edge (u, v) ∈ E // Loop through all edges 1 -10
E ∞
3. Relax(u, v) 1
7

Relax(B, D)
B C
1. if dist[B] + w(B, D) = 1 + 1 < ∞ = dist[D] // If found a shorter path to v 1 10
2. dist[D] ← dist[B] + w(B, D) // Update distance to v
3. prev[D] ← B // Update predecessor of v

111
 Example (6/9)
A B C D E 𝑉 = 𝐴, 𝐵, 𝐶, 𝐷, 𝐸
0, 𝐴 1, 𝐴 10, 𝐴 0, 𝐶 ∞, − 𝐸= 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐵, 𝐷 , 𝐶, 𝐷 , 𝐷, 𝐸 , 𝐸, 𝐶
𝐶, 𝐷
true lowest cost
4 0 0
A D 5
1. for i ← 1 to |V| − 1 // Step 2: Relax edges |V| - 1 times𝑖=1 10
2. for each edge (u, v) ∈ E // Loop through all edges 1 -10
E ∞
3. Relax(u, v) 1
7

Relax(C, D)
B C
1. if dist[C] + w(C, D) = 10 - 10 < 2 = dist[D] // If found a shorter path to v 1 10
2. dist[D] ← dist[C] + w(C, D) // Update distance to v
3. prev[D] ← C // Update predecessor of v

112
 Example (7/9)
A B C D E 𝑉 = 𝐴, 𝐵, 𝐶, 𝐷, 𝐸
0, 𝐴 1, 𝐴 10, 𝐴 0, 𝐶 5, 𝐷 𝐸= 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐵, 𝐷 , 𝐶, 𝐷 , 𝐷, 𝐸 , 𝐸, 𝐶
𝐷, 𝐸
true lowest cost
4 0 0
A D 5
1. for i ← 1 to |V| − 1 𝑖=1
// Step 2: Relax edges |V| - 1 times 10
2. for each edge (u, v) ∈ E // Loop through all edges 1 -10
E 5
3. Relax(u, v) 1
7

Relax(D, E)
B C
1. if dist[D] + w(D, E) = 0 + 5 < ∞ = dist[E] // If found a shorter path to v 1 10
2. dist[E] ← dist[D] + w(D, E) // Update distance to v
3. prev[E] ← D // Update predecessor of v

113
 Example (8/9)
A B C D E 𝑉 = 𝐴, 𝐵, 𝐶, 𝐷, 𝐸
0, 𝐴 1, 𝐴 10, 𝐴 0, 𝐶 5, 𝐷 𝐸= 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐵, 𝐷 , 𝐶, 𝐷 , 𝐷, 𝐸 , 𝐸, 𝐶
𝐸, 𝐶
UNCHANGED
4 0 0
A D 5
1. for i ← 1 to |V| − 1 𝑖=1
// Step 2: Relax edges |V| - 1 times 10
2. for each edge (u, v) ∈ E // Loop through all edges 1 -10
E 5
3. Relax(u, v) 1
7

Relax(E, C)
B C
1. if dist[E] + w(E, C) = 5 + 7 < 10 = dist[C] // If found a shorter path to v 1 10
2. dist[E] ← dist[E] + w(E, C) // Update distance to v
3. prev[C] ← E // Update predecessor of v

114
 Example (3/9)
A B C D E 𝑉 = 𝐴, 𝐵, 𝐶, 𝐷, 𝐸
0, 𝐴 1, 𝐴 10, 𝐴 0, 𝐶 5, 𝐷 𝐸= 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐵, 𝐷 , 𝐶, 𝐷 , 𝐷, 𝐸 , 𝐸, 𝐶
𝐴, 𝐵
UNCHANGED
4 0 0
A D 5
1. for i ← 1 to |V| − 1 𝑖=2
// Step 2: Relax edges |V| - 1 times 10
2. for each edge (u, v) ∈ E // Loop through all edges 1 -10
E 5
3. Relax(u, v) 1
7

Relax(A, B)
B C
1. if dist[A] + w(A, B) = 0 + 1 < 1 = dist[B] // If found a shorter path to v 1 10
2. dist[B] ← dist[A] + w(A, B) // Update distance to v
3. prev[B] ← A // Update predecessor of v

115
 Example (4/9)
A B C D E 𝑉 = 𝐴, 𝐵, 𝐶, 𝐷, 𝐸
0, 𝐴 1, 𝐴 10, 𝐴 0, 𝐶 5, 𝐷 𝐸= 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐵, 𝐷 , 𝐶, 𝐷 , 𝐷, 𝐸 , 𝐸, 𝐶
𝐴, 𝐶
UNCHANGED
4 0 0
A D 5
1. for i ← 1 to |V| − 1 𝑖=2
// Step 2: Relax edges |V| - 1 times 10
2. for each edge (u, v) ∈ E // Loop through all edges 1 -10
E 5
3. Relax(u, v) 1
7

Relax(u, v)
B C
1. if dist[A] + w(A, C) = 0 + 10 < 10 = dist[C] // If found a shorter path to v 1 10
2. dist[C] ← dist[A] + w(A, C) // Update distance to v
3. prev[C] ← A // Update predecessor of v

116
 Example (5/9)
A B C D E 𝑉 = 𝐴, 𝐵, 𝐶, 𝐷, 𝐸
0, 𝐴 1, 𝐴 10, 𝐴 0, 𝐶 5, 𝐷 𝐸= 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐵, 𝐷 , 𝐶, 𝐷 , 𝐷, 𝐸 , 𝐸, 𝐶
𝐵, 𝐷
UNCHANGED
4 0 0
A D 5
1. for i ← 1 to |V| − 1 𝑖=2
// Step 2: Relax edges |V| - 1 times 10
2. for each edge (u, v) ∈ E // Loop through all edges 1 -10
E 5
3. Relax(u, v) 1
7

Relax(B, D)
B C
1. if dist[B] + w(B, D) = 1 + 1 < 0 = dist[D] // If found a shorter path to v 1 10
2. dist[D] ← dist[B] + w(B, D) // Update distance to v
3. prev[D] ← B // Update predecessor of v

117
 Example (6/9)
A B C D E 𝑉 = 𝐴, 𝐵, 𝐶, 𝐷, 𝐸
0, 𝐴 1, 𝐴 10, 𝐴 0, 𝐶 ∞, − 𝐸= 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐵, 𝐷 , 𝐶, 𝐷 , 𝐷, 𝐸 , 𝐸, 𝐶
𝐶, 𝐷
UNCHANGED
4 0 0
A D 5
1. for i ← 1 to |V| − 1 // Step 2: Relax edges |V| - 1 times𝑖=2 10
2. for each edge (u, v) ∈ E // Loop through all edges 1 -10
E ∞
3. Relax(u, v) 1
7

Relax(C, D)
B C
1. if dist[C] + w(C, D) = 10 - 10 < 0 = dist[D] // If found a shorter path to v 1 10
2. dist[D] ← dist[C] + w(C, D) // Update distance to v
3. prev[D] ← C // Update predecessor of v

118
 Example (7/9)
A B C D E 𝑉 = 𝐴, 𝐵, 𝐶, 𝐷, 𝐸
0, 𝐴 1, 𝐴 10, 𝐴 0, 𝐶 5, 𝐷 𝐸= 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐵, 𝐷 , 𝐶, 𝐷 , 𝐷, 𝐸 , 𝐸, 𝐶
𝐷, 𝐸
UNCHANGED
4 0 0
A D 5
1. for i ← 1 to |V| − 1 𝑖=2
// Step 2: Relax edges |V| - 1 times 10
2. for each edge (u, v) ∈ E // Loop through all edges 1 -10
E 5
3. Relax(u, v) 1
7

Relax(D, E)
B C
1. if dist[D] + w(D, E) = 0 + 5 < 5 = dist[E] // If found a shorter path to v 1 10
2. dist[E] ← dist[D] + w(D, E) // Update distance to v
3. prev[E] ← D // Update predecessor of v

119
 Example (8/9)
A B C D E 𝑉 = 𝐴, 𝐵, 𝐶, 𝐷, 𝐸
0, 𝐴 1, 𝐴 10, 𝐴 0, 𝐶 5, 𝐷 𝐸= 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐵, 𝐷 , 𝐶, 𝐷 , 𝐷, 𝐸 , 𝐸, 𝐶
𝐸, 𝐶
UNCHANGED
4 0 0
A D 5
1. for i ← 1 to |V| − 1 𝑖=2
// Step 2: Relax edges |V| - 1 times 10
2. for each edge (u, v) ∈ E // Loop through all edges 1 -10
E 5
3. Relax(u, v) 1
7

Relax(E, C)
B C
1. if dist[E] + w(E, C) = 5 + 7 < 10 = dist[C] // If found a shorter path to v 1 10
2. dist[E] ← dist[E] + w(E, C) // Update distance to v
3. prev[C] ← E // Update predecessor of v

120
 Example (9/9)
A B C D E 𝑉 = 𝐴, 𝐵, 𝐶, 𝐷, 𝐸
0, 𝐴 1, 𝐴 10, 𝐴 0, 𝐶 5, 𝐷

The cost for each vertex remains unchanged

4 0 0
A D 5
1. for i ← 1 to |V| − 1 𝑖 = 2,3,4
// Step 2: Relax edges |V| - 1 times 10
2. for each edge (u, v) ∈ E // Loop through all edges 1 -10
E 5
3. Relax(u, v) 1
7
B C
1 10

121
 Example (9/9)
A B C D E 𝑉 = 𝐴, 𝐵, 𝐶, 𝐷, 𝐸
0, 𝐴 1, 𝐴 10, 𝐴 0, 𝐶 5, 𝐷

NO negative-weight cycles
0 0
A D 5
1. for each edge (u, v) ∈ E // Step 3: Check for negative-weight cycles 10
2. if dist[v] > dist[u] + w(u, v) // If still can relax an edge, cycle exists 1 -10
E 5
3. return false // Negative-weight cycle detected 1
4. return true // No negative cycle, algorithm successful 7
B C
1 10
Shortest path from A to E is: A→C→D→E (EDCA)
Cost: 5
122
Correctness
• Loop invariant: After iteration i, all vertices with shortest paths from s of length i
edges or less have correct distances.

123
Complexity
Bellman-Ford(G, s)

1. for all v ∈ V // Step 1: Initialize distances and predecessors Relax(u, v)

2. dist[v] ← ∞ // Set all distances to infinity (unreachable at start) 1. if dist[v] > dist[u] + w(u, v) // If found a shorter path to v
2. dist[v] ← dist[u] + w(u, v) // Update distance to v
3. prev[v] ← null // No predecessor yet
3. prev[v] ← u // Update predecessor of v
4. dist[s] ← 0 // Distance to source is 0

5. for i ← 1 to |V| − 1 // Step 2: Relax edges |V| - 1 times 3

6. for each edge (u, v) ∈ E // Loop through all edges
𝑂 𝑉 𝐸 =𝑂 𝑉
7. Relax(u, v)

8. for each edge (u, v) ∈ E // Step 3: Check for negative-weight cycles

9. if dist[v] > dist[u] + w(u, v) // If still can relax an edge, cycle exists

10. return false // Negative-weight cycle detected

𝑂 𝐸
11. return true // No negative cycle, algorithm successful

124
How about this graph?
• Find the shortest path from A to E by Bellman-Ford algorithm.

A D 5
10
1 -10
E
1
-7
B C

125
Outline
1. BFS algorithm

2. Dijkstra’s algorithm

3. Bellman–Ford Algorithm

4. Floyd–Warshall algorithm

12
6
 History

Robert (Bob) W Floyd Warshall, Stephen

(1936–2001) (1935–2006)
[Link]/award_winners/floyd_3720707.cfm Wikipedia

• The Floyd–Warshall algorithm is a dynamic programming algorithm used to find the shortest paths between all
pairs of vertices in a weighted graph. It works for both directed and undirected graphs, and it can handle negative
edge weights (but not negative weight cycles).
• It was developed in 1956 by the American scientists Floyd R. W. [1] and Warshall S. [2] in 1962.
– Robert W Floyd won the Turing award in 1978 for having a clear influence on methodologies for the creation of efficient and reliable
software, and for helping to found the following important subfields of computer science: the theory of parsing, the semantics of
programming languages, automatic program verification, automatic program synthesis, and analysis of algorithms.

[1] Floyd, Robert W. Algorithm 97: shortest path. Communications of the ACM 5.6 (1962): 345-345.
[2] Warshall, Stephen. A theorem on boolean matrices. Journal of the ACM (JACM) 9.1 (1962): 11-12. 127
(More) History: (Kleene-Roy-)Floyd-Warshall(-Ingerman)
• Floyd-Warshall algorithm was independently and simultaneously developed by Kleene in 1956
[1], Roy in 1959 [2], and Floyd [3] and Ingerman [4] both in 1962.

• Core Idea: Dynamic Programming

– Floyd-Warshall algorithm iteratively builds up a distance matrix,
– At each iteration 𝑘, the algorithm considers whether a shorter path between vertex 𝑖 and vertex 𝑗 can be found by
passing through vertex 𝑘 as an intermediate vertex,
– If the shortest path from 𝑖 to 𝑗 goes through vertex 𝑘, then the sub-paths from 𝑖 to 𝑘 and from 𝑘 to 𝑗 must also be
shortest paths.

[1] Kleene, S. C. (1956). Representation of events in nerve nets and finite automata. In C. E. Shannon & J. McCarthy (Eds.), Automata
Studies (pp. 3–41). Princeton University Press.
[2] Roy, B. (1959). Transitivité et connexité. Comptes Rendus de l'Académie des Sciences, 249(23), 2496–2498.
[3] Floyd, R. W. (1962). Algorithm 97: Shortest Path. Communications of the ACM, 5(6), 345.
[4] Warshall, Stephen. A theorem on boolean matrices. Journal of the ACM (JACM) 9.1 (1962): 11-12.
[5] Ingerman, P. Z. (1962). Algorithm 104: Path Matrix. Communications of the ACM, 5(11), 556.
128
What is Dynamic Programming?

• It is an algorithm design paradigm

– like divide-and-conquer is an algorithm design paradigm.
• Usually it is for solving optimization problems
– eg, shortest path

129
Elements of dynamic programming

• Big problems break up into little problems.

– eg, shortest path with at most 𝑘 edges.
• The optimal solution of a problem can be expressed in
terms of optimal solutions of smaller sub-problems.
– Eg,

We call this “optimal sub-structure”

130
Elements of dynamic programming

• The sub-problems overlap a lot.

We call this “overlapping sub-problems”

131
Elements of dynamic programming

• Optimal substructure.
– Optimal solutions to sub-problems are sub-solutions to the
optimal solution of the original problem.
• Overlapping subproblems.
– The subproblems show up again and again.

132
Elements of dynamic programming

• Using these properties, we can design a dynamic

programming algorithm:
– Keep a table of solutions to the smaller problems.
– Use the solutions in the table to solve bigger problems.
– At the end we can use information we collected along the way
to find the optimal solution.
• eg, recover the shortest path (not just its cost).

133
 Top down
Bottom up

Two ways to think about and/or implement DP algorithms

2 2 1 1
1 1 1 1 2 2 2 2

0 0 0 0 0 0 0 0
ott om up(sift Down) Top down(sift p)
he
Tnu
mb
erinth
eircc
lein
dic
ate
sth
ema
imu
xmti m
es
ofs
wa
pp
ing
req
uire
dw
he
na
dd
ing
the
no
de
tothe
he
p.
a

134
Bottom-Up approach

• What we just saw.

• Solve the small problems first
• Then bigger problems
• …
• Then bigger problems
• Then finally solve the real problem.

135
Top-Down approach

• Think of it like a recursive algorithm.

• To solve the big problem:
– Recurse to solve smaller problems
• Those recurse to solve smaller problems
– etc..

• The difference from divide and conquer:

– Memo-ization
– Keep track of what small problems you’ve already solved to
prevent re-solving the same problem twice.

136
Back to: Floyd-Warshall Algorithm

• Naïve solution (if we want to handle negative edge

weights):
– For all s in G:
• Run Bellman-Ford on G starting at s.
– Time 𝑂 𝑛 ⋅ 𝑛𝑚 = 𝑂(𝑛2 ⋅ 𝑚),
• may be as bad as 𝑛4 if 𝑚 = 𝑛2 !!!
• Can we do better ? ☺

138
Back to: Floyd-Warshall Algorithm

• Naïve solution (if we want to handle negative edge

weights):
– For all s in G:
• Run Bellman-Ford on G starting at s.
– Time 𝑂 𝑛 ⋅ 𝑛𝑚 = 𝑂(𝑛2 ⋅ 𝑚),
• may be as bad as 𝑛4 if 𝑚 = 𝑛2 !!!
• Can we do better ? ☺ The answer is YES.

139
Optimal substructure

• Sub-problem: For all pairs (𝑢, 𝑣), find the cost of the
shortest path from 𝑢 to 𝑣, so that all the internal vertices
on that path are in {1, … , 𝑘 − 1}
• Let 𝐷 (𝑘−1) [𝑢, 𝑣] be the solution to this sub-problem
k k+1
u

2 1 v
3

n Vertices {1, … , 𝑘 − 1}
… k-1
140
Optimal substructure

• Sub-problem:Our ForDP all pairswill

algorithm (𝑢,fill𝑣), find
in the the cost of the
n-by-n
shortest patharray
from 𝑢, 𝐷to(1)𝑣,
𝐷(0) , … ,so thatiteratively
𝐷(𝑛−1) all theandinternal vertices
then we’ll be done.
on that path are in {1, … , 𝑘 − 1}
• Let 𝐷 (𝑘−1) [𝑢, 𝑣] be the solution to this sub-problem
k k+1
This is the
u shortest path
from u to v
2 1 v through the
3
blue set. It has
length
n Vertices {1, … , 𝑘 − 1} 𝐷 (𝑘−1) [𝑢, 𝑣]
… k-1
141
Optimal substructure

• Sub-problem: For all pairs (𝑢, 𝑣),(𝑘)find the cost of the

Question: How can we find 𝐷 [𝑢, 𝑣] by
shortest path from 𝑢 to 𝑣,𝐷so
using that
(𝑘−1) [𝑢, 𝑣]all the internal vertices
on that path are in {1, … , 𝑘 − 1}
• Let 𝐷 (𝑘−1) [𝑢, 𝑣] be the solution to this sub-problem
k k+1
This is the
u shortest path
from u to v
2 1 v through the
3
blue set. It has
length
n Vertices {1, … , 𝑘 − 1} 𝐷 (𝑘−1) [𝑢, 𝑣]
… k-1
142
How can we find 𝐷 (𝑘) [𝑢, 𝑣] by using 𝐷 (𝑘−1) [𝑢, 𝑣

𝐷 (𝑘) [𝑢, 𝑣] is the cost the shortest path from 𝑢 to 𝑣 so that all
internal vertices on that path are in {1, … , 𝑘}.
Vertices {1, … , 𝑘}

k k+1
u

2 1 v
3

n Vertices {1, … , 𝑘 − 1}
… k-1

143
How can we find 𝐷 (𝑘) [𝑢, 𝑣] by using 𝐷 (𝑘−1) [𝑢, 𝑣

Case 1: we don’t need vertex 𝑘.

𝐷(𝑘) [𝑢, 𝑣] = 𝐷(𝑘−1) [𝑢, 𝑣]
Vertices {1, … , 𝑘}

k k+1 This was

u the
shortest
2 1 v
3 path
before, so
n Vertices 1, …, k - 1
k-1
it’s still the
…
shortest
path now.
144
How can we find 𝐷 (𝑘) [𝑢, 𝑣] by using 𝐷 (𝑘−1) [𝑢, 𝑣

Case 2: we need vertex 𝑘.

Vertices {1, … , 𝑘}

k k+1
u

2 1 v
3

n Vertices {1, … , 𝑘 − 1}
… k-1

145
How can we find 𝐷 (𝑘) [𝑢, 𝑣] by using 𝐷 (𝑘−1) [𝑢, 𝑣
Suppose there are no negative cycles. Then
Case 2: we need vertex 𝑘. WLOG the shortest path from 𝑢 to 𝑣 through
{1, … , 𝑘} is simple.
Vertices {1, … , 𝑘}

k k+1
u

2 1 v
3

n Vertices {1, … , 𝑘 − 1}
… k-1

146
How can we find 𝐷 (𝑘) [𝑢, 𝑣] by using 𝐷 (𝑘−1) [𝑢, 𝑣

Case 2: we need vertex 𝑘. If that path passes through 𝑘, it must look like
this:
Vertices {1, … , 𝑘}

k k+1
u

2 1 v
3

n Vertices {1, … , 𝑘 − 1}
… k-1

147
How can we find 𝐷 (𝑘) [𝑢, 𝑣] by using 𝐷 (𝑘−1) [𝑢, 𝑣
This path shortest path from 𝑢 to 𝑣 through
Case 2: we need vertex 𝑘. {1, … , 𝑘 − 1}
• sub-paths of shortest paths are shortest
Vertices {1, … , 𝑘} paths

k k+1
u

2 1 v
3

n Vertices {1, … , 𝑘 − 1}
… k-1

148
How can we find 𝐷 (𝑘) [𝑢, 𝑣] by using 𝐷 (𝑘−1) [𝑢, 𝑣
Same for this path
Case 2: we need vertex 𝑘.

Vertices {1, … , 𝑘}

k k+1
u

2 1 v
3

n Vertices {1, … , 𝑘 − 1}
… k-1

149
How can we find 𝐷 (𝑘) [𝑢, 𝑣] by using 𝐷 (𝑘−1) [𝑢, 𝑣
So that,
Case 2: we need vertex 𝑘. 𝐷(𝑘) 𝑢, 𝑣 = 𝐷(𝑘−1) 𝑢, 𝑘 + 𝐷(𝑘−1) [𝑘, 𝑣]

Vertices {1, … , 𝑘}

k k+1
u

2 1 v
3

n Vertices {1, … , 𝑘 − 1}
… k-1

150
 How can we find 𝐷 (𝑘) [𝑢, 𝑣] by using 𝐷 (𝑘−1) [𝑢, 𝑣]?
Case 1: cost of shortest path
through {1, … , 𝑘 − 1}

𝐷 (𝑘) 𝑢, 𝑣 = min(𝐷 𝑘
𝑢, 𝑣 , 𝐷 𝑘−1
𝑢, 𝑘 + 𝐷 𝑘−1
𝑘, 𝑣 )

Case 2: Cost of shortest path from

𝑢 to 𝑘 and then from 𝑘 to 𝑣
{1, … , 𝑘 − 1}

151
 How can we find 𝐷 (𝑘) [𝑢, 𝑣] by using 𝐷 (𝑘−1) [𝑢, 𝑣]?
Case 1: cost of shortest path Case 2: Cost of shortest path from
through {1, … , 𝑘 − 1} 𝑢 to 𝑘 and then from 𝑘 to 𝑣
{1, … , 𝑘 − 1}

𝐷 (𝑘) 𝑢, 𝑣 = min(𝐷 𝑘 𝑢, 𝑣 , 𝐷 𝑘−1

𝑢, 𝑘 + 𝐷 𝑘−1
𝑘, 𝑣 )
• Optimal substructure:
– We can solve the big problem using smaller problems.
• Overlapping sub-problems:
– 𝐷 𝑘−1 𝑢, 𝑘 can be used to help compute 𝐷(𝑘) 𝑢, 𝑣 for lots of
different u’s.

152
Floyd-Warshall algorithm

• Step 1: Initialize n-by-n arrays 𝐷 (𝑘) 𝑢, 𝑣 for 𝑘 = 0, … , 𝑛

– 𝐷(𝑘) 𝑢, 𝑢 = 0 for all 𝑢, for all 𝑘
– 𝐷(𝑘) 𝑢, 𝑣 = ∞ for all 𝑢 ≠ 𝑣, for all 𝑘
– 𝐷(0) 𝑢, 𝑣 = 𝑤(𝑢, 𝑣) for all (𝑢, 𝑣) in edge set 𝐸.

The base case checks out: the only path through zero other
vertices are edges directly from u to v.

153
Floyd-Warshall algorithm

• Step 2: For 𝑘 = 1, … , 𝑛
– For pairs (𝑢, 𝑣) in 𝑉 × 𝑉 do

𝐷(𝑘) 𝑢, 𝑣 = min(𝐷 𝑘
𝑢, 𝑣 , 𝐷 𝑘−1
𝑢, 𝑘 + 𝐷 𝑘−1
𝑘, 𝑣 )

– Return 𝐷(𝑛) [𝑢, 𝑣]

This is a bottom-up Dynamic Programming algorithm. ☺

154
Full Pseudocode for Floyd-Warshall
1. Floyd_Warshall(G): //G is the graph, w(u,v): weight of edge (u,v) to save the
2. N = number_of_vertices_in(G) shortest distance
3. dist[N][N] ← ∞ // Distance matrix is initially infinite
4. pred[N][N] ← NULL // No predecessor yet

5. for all vertices i:

6. for all vertices j: the predecessor node
7. dist[i, j] ← w(i, j) // Direct edge weight or ∞ (0 if i=j) (for path reconstruction)
8. pred[i, j] = i if dist[i, j] != ∞

9. // k - intermediate vertex, i - source vertex, j - destination vertex

10. for k ← 1 to V:
11. for all vertices i:
12. for all vertices j:
13. // Relaxation: Check if path i → k → j is shorter
14. if dist[i, k] != ∞ and dist[k, j] != ∞ and dist[i, k] + dist[k, j] < dist[i, j]:
15. dist[i, j] ← dist[i, k] + dist[k, j]
16. pred[i, j] ← pred[k, j]
Example
Given a connected undirected graph G with non-negative weights on the edges, find the shortest path for each
pair of vertices (X, Y).

F
14
9
8
9
E G I
10
6 7
9
1 11 7
A D
12
2
5
4
H 6
J

B 3
C
156
 Example: Initialization
1. for all vertices i: dist / prev
2. for all vertices j:
3. dist[i, j] ← w(i, j) // Direct edge weight or ∞ (0 if i=j)
4. pred[i, j] = i if dist[i, j] != ∞

A (0) B (1) C (2) D (3) E (4) F (5) G (6) H (7) I (8) J (9)
A (0) 0/0 2/0 5/0 1/0 6/0 ∞/N ∞/N ∞/N ∞/N ∞/N
B (1) 2/1 0/1 3/1 ∞/N ∞/N ∞/N ∞/N ∞/N ∞/N ∞/N
C (2) 5/2 3/2 0/2 4/2 ∞/N ∞/N ∞/N ∞/N ∞/N ∞/N F
9 14
D (3) 1 / 3 ∞ / N 4 / 3 0 / 3 10 / 3 ∞ / N 7 / 3 12 / 3 ∞ / N ∞ / N 8
9
E (4) 6 / 4 ∞ / N ∞ / N 10 / 4 0 / 4 9 / 4 ∞ / N ∞ / N ∞ / N ∞ / N E G I
10 7
F (5) ∞ / N ∞ / N ∞ / N ∞ / N 9 / 5 0 / 5 8 / 5 ∞ / N 14 / 5 ∞ / N 6 9
1 11 7
G (6) ∞ / N ∞ / N ∞ / N 7 / 6 ∞ / N 8 / 6 0 / 6 11 / 6 9 / 6 ∞ / N A D
H (7) ∞ / N ∞ / N ∞ / N 12 / 7 ∞ / N ∞ / N 11 / 7 0 / 7 9 / 7 6 / 7 2 5
4
12 H 6
J
I (8) ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N 14 / 8 9 / 8 9 / 8 0 / 8 7 / 8
J (9) ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N 6 / 9 7 / 9 0 / 9 B 3
C 157
 Example: Initialization
1. for all vertices i: dist / prev
2. for all vertices j:
3. dist[i, j] ← w(i, j) // Direct edge weight or ∞ (0 if i=j)
4. pred[i, j] = i if dist[i, j] != ∞

A (0) B (1) C (2) D (3) E (4) F (5) G (6) H (7) I (8) J (9)
A (0) 0/0 2/0 5/0 1/0 6/0 ∞/N ∞/N ∞/N ∞/N ∞/N
B (1) 2/1 0/1 3/1 ∞/N ∞/N ∞/N ∞/N ∞/N ∞/N ∞/N
C (2) 5/2 3/2 0/2 4/2 ∞/N ∞/N ∞/N ∞/N ∞/N ∞/N F
9 14
D (3) 1 / 3 ∞ / N 4 / 3 0 / 3 10 / 3 ∞ / N 7 / 3 12 / 3 ∞ / N ∞ / N 8
9
E (4) 6 / 4 ∞ / N ∞ / N 10 / 4 0 / 4 9 / 4 ∞ / N ∞ / N ∞ / N ∞ / N E G I
10 7
F (5) ∞ / N ∞ / N ∞ / N ∞ / N 9 / 5 0 / 5 8 / 5 ∞ / N 14 / 5 ∞ / N 6 9
1 11 7
G (6) ∞ / N ∞ / N ∞ / N 7 / 6 ∞ / N 8 / 6 0 / 6 11 / 6 9 / 6 ∞ / N A D
H (7) ∞ / N ∞ / N ∞ / N 12 / 7 ∞ / N ∞ / N 11 / 7 0 / 7 9 / 7 6 / 7 2 5
4
12 H 6
J
I (8) ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N 14 / 8 9 / 8 9 / 8 0 / 8 7 / 8
J (9) ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N 6 / 9 7 / 9 0 / 9 B 3
C 158
 Example: k = 0 (A)
Consider path through vertex A:
dist[1, 3] = dist[1, 0] + dist[0, 3] = 2 + 1 = 3
• 𝐵 → 𝐷:
prev[1, 3] = prev[0, 3] = 0
• 𝐵 → 𝐴 → 𝐷: 2 + 1 = 3 < ∞ (OK)

A (0) B (1) C (2) D (3) E (4) F (5) G (6) H (7) I (8) J (9)
A (0) 0/0 2/0 5/0 1/0 6/0 ∞/N ∞/N ∞/N ∞/N ∞/N
B (1) 2/1 0/1 3/1 3/0 ∞/N ∞/N ∞/N ∞/N ∞/N ∞/N
C (2) 5/2 3/2 0/2 4/2 ∞/N ∞/N ∞/N ∞/N ∞/N ∞/N F
9 14
D (3) 1 / 3 ∞ / N 4 / 3 0 / 3 10 / 3 ∞ / N 7 / 3 12 / 3 ∞ / N ∞ / N 8
9
E (4) 6 / 4 ∞ / N ∞ / N 10 / 4 0 / 4 9 / 4 ∞ / N ∞ / N ∞ / N ∞ / N E G I
10 7
F (5) ∞ / N ∞ / N ∞ / N ∞ / N 9 / 5 0 / 5 8 / 5 ∞ / N 14 / 5 ∞ / N 6 9
1 11 7
G (6) ∞ / N ∞ / N ∞ / N 7 / 6 ∞ / N 8 / 6 0 / 6 11 / 6 9 / 6 ∞ / N A D
H (7) ∞ / N ∞ / N ∞ / N 12 / 7 ∞ / N ∞ / N 11 / 7 0 / 7 9 / 7 6 / 7 2 5
4
12 H 6
J
I (8) ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N 14 / 8 9 / 8 9 / 8 0 / 8 7 / 8
J (9) ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N 6 / 9 7 / 9 0 / 9 B 3
C 159
 Example: k = 0 (A)
Consider path through vertex A:
We DO NOT update here.
• 𝐵 → 𝐶:
• 𝐵 → 𝐴 → 𝐶: 2 + 5 = 7 > 3 (NOT OK)

A (0) B (1) C (2) D (3) E (4) F (5) G (6) H (7) I (8) J (9)
A (0) 0/0 2/0 5/0 1/0 6/0 ∞/N ∞/N ∞/N ∞/N ∞/N
B (1) 2/1 0/1 3/1 3/0 ∞/N ∞/N ∞/N ∞/N ∞/N ∞/N
C (2) 5/2 3/2 0/2 4/2 ∞/N ∞/N ∞/N ∞/N ∞/N ∞/N F
9 14
D (3) 1 / 3 ∞ / N 4 / 3 0 / 3 10 / 3 ∞ / N 7 / 3 12 / 3 ∞ / N ∞ / N 8
9
E (4) 6 / 4 ∞ / N ∞ / N 10 / 4 0 / 4 9 / 4 ∞ / N ∞ / N ∞ / N ∞ / N E G I
10 7
F (5) ∞ / N ∞ / N ∞ / N ∞ / N 9 / 5 0 / 5 8 / 5 ∞ / N 14 / 5 ∞ / N 6 9
1 11 7
G (6) ∞ / N ∞ / N ∞ / N 7 / 6 ∞ / N 8 / 6 0 / 6 11 / 6 9 / 6 ∞ / N A D
H (7) ∞ / N ∞ / N ∞ / N 12 / 7 ∞ / N ∞ / N 11 / 7 0 / 7 9 / 7 6 / 7 2 5
4
12 H 6
J
I (8) ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N 14 / 8 9 / 8 9 / 8 0 / 8 7 / 8
J (9) ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N 6 / 9 7 / 9 0 / 9 B 3
C 160
 Example: k = 0 (A)
Consider path through vertex A:
dist[1, 4] = dist[1, 0] + dist[0, 4] = 2 + 6 = 8
• 𝐵 → 𝐸:
prev[1, 4] = prev[0, 4] = 0
• 𝐵 → 𝐴 → 𝐸: 2 + 6 = 8 < ∞ (OK)

A (0) B (1) C (2) D (3) E (4) F (5) G (6) H (7) I (8) J (9)
A (0) 0/0 2/0 5/0 1/0 6/0 ∞/N ∞/N ∞/N ∞/N ∞/N
B (1) 2/1 0/1 3/1 3/0 8/0 ∞/N ∞/N ∞/N ∞/N ∞/N
C (2) 5/2 3/2 0/2 4/2 ∞/N ∞/N ∞/N ∞/N ∞/N ∞/N F
9 14
D (3) 1 / 3 ∞ / N 4 / 3 0 / 3 10 / 3 ∞ / N 7 / 3 12 / 3 ∞ / N ∞ / N 8
9
E (4) 6 / 4 ∞ / N ∞ / N 10 / 4 0 / 4 9 / 4 ∞ / N ∞ / N ∞ / N ∞ / N E G I
10 7
F (5) ∞ / N ∞ / N ∞ / N ∞ / N 9 / 5 0 / 5 8 / 5 ∞ / N 14 / 5 ∞ / N 6 9
1 11 7
G (6) ∞ / N ∞ / N ∞ / N 7 / 6 ∞ / N 8 / 6 0 / 6 11 / 6 9 / 6 ∞ / N A D
H (7) ∞ / N ∞ / N ∞ / N 12 / 7 ∞ / N ∞ / N 11 / 7 0 / 7 9 / 7 6 / 7 2 5
4
12 H 6
J
I (8) ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N 14 / 8 9 / 8 9 / 8 0 / 8 7 / 8
J (9) ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N 6 / 9 7 / 9 0 / 9 B 3
C 161
 Example: k = 0 (A)
Consider path through vertex A:
We DO NOT update here.
• 𝐶 → 𝐷:
• C → 𝐴 → 𝐷: 5 + 1 = 6 > 4 (NOT OK)

A (0) B (1) C (2) D (3) E (4) F (5) G (6) H (7) I (8) J (9)
A (0) 0/0 2/0 5/0 1/0 6/0 ∞/N ∞/N ∞/N ∞/N ∞/N
B (1) 2/1 0/1 3/1 3/0 8/0 ∞/N ∞/N ∞/N ∞/N ∞/N
C (2) 5/2 3/2 0/2 4/2 ∞/N ∞/N ∞/N ∞/N ∞/N ∞/N F
9 14
D (3) 1 / 3 ∞ / N 4 / 3 0 / 3 10 / 3 ∞ / N 7 / 3 12 / 3 ∞ / N ∞ / N 8
9
E (4) 6 / 4 ∞ / N ∞ / N 10 / 4 0 / 4 9 / 4 ∞ / N ∞ / N ∞ / N ∞ / N E G I
10 7
F (5) ∞ / N ∞ / N ∞ / N ∞ / N 9 / 5 0 / 5 8 / 5 ∞ / N 14 / 5 ∞ / N 6 9
1 11 7
G (6) ∞ / N ∞ / N ∞ / N 7 / 6 ∞ / N 8 / 6 0 / 6 11 / 6 9 / 6 ∞ / N A D
H (7) ∞ / N ∞ / N ∞ / N 12 / 7 ∞ / N ∞ / N 11 / 7 0 / 7 9 / 7 6 / 7 2 5
4
12 H 6
J
I (8) ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N 14 / 8 9 / 8 9 / 8 0 / 8 7 / 8
J (9) ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N 6 / 9 7 / 9 0 / 9 B 3
C 162
 Example: k = 0 (A)
Consider path through vertex A:
dist[2, 4] = dist[2, 0] + dist[0, 4] = 5 + 6 = 11
• 𝐶 → 𝐸:
prev[2, 4] = prev[0, 4] = 0
• C → 𝐴 → 𝐸: 5 + 6 = 11 < ∞ (OK)

A (0) B (1) C (2) D (3) E (4) F (5) G (6) H (7) I (8) J (9)
A (0) 0/0 2/0 5/0 1/0 6/0 ∞/N ∞/N ∞/N ∞/N ∞/N
B (1) 2/1 0/1 3/1 3/0 8/0 ∞/N ∞/N ∞/N ∞/N ∞/N
C (2) 5 / 2 3 / 2 0 / 2 4 / 2 11 / 0 ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N F
9 14
D (3) 1 / 3 ∞ / N 4 / 3 0 / 3 10 / 3 ∞ / N 7 / 3 12 / 3 ∞ / N ∞ / N 8
9
E (4) 6 / 4 ∞ / N ∞ / N 10 / 4 0 / 4 9 / 4 ∞ / N ∞ / N ∞ / N ∞ / N E G I
10 7
F (5) ∞ / N ∞ / N ∞ / N ∞ / N 9 / 5 0 / 5 8 / 5 ∞ / N 14 / 5 ∞ / N 6 9
1 11 7
G (6) ∞ / N ∞ / N ∞ / N 7 / 6 ∞ / N 8 / 6 0 / 6 11 / 6 9 / 6 ∞ / N A D
H (7) ∞ / N ∞ / N ∞ / N 12 / 7 ∞ / N ∞ / N 11 / 7 0 / 7 9 / 7 6 / 7 2 5
4
12 H 6
J
I (8) ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N 14 / 8 9 / 8 9 / 8 0 / 8 7 / 8
J (9) ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N 6 / 9 7 / 9 0 / 9 B 3
C 163
 Example: k = 0 (A)
Consider path through vertex A:
dist[3, 1] = dist[3, 0] + dist[0, 1] = 1 + 2 = 3
• 𝐷 → 𝐵:
prev[3, 1] = prev[0, 1] = 0
• D → 𝐴 → 𝐵: 1 + 2 = 3 < ∞ (OK)

A (0) B (1) C (2) D (3) E (4) F (5) G (6) H (7) I (8) J (9)
A (0) 0/0 2/0 5/0 1/0 6/0 ∞/N ∞/N ∞/N ∞/N ∞/N
B (1) 2/1 0/1 3/1 3/0 8/0 ∞/N ∞/N ∞/N ∞/N ∞/N
C (2) 5 / 2 3 / 2 0 / 2 4 / 2 11 / 0 ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N F
9 14
D (3) 1/3 3/0 4 / 3 0 / 3 10 / 3 ∞ / N 7 / 3 12 / 3 ∞ / N ∞ / N 8
9
E (4) 6 / 4 ∞ / N ∞ / N 10 / 4 0 / 4 9 / 4 ∞ / N ∞ / N ∞ / N ∞ / N E G I
10 7
F (5) ∞ / N ∞ / N ∞ / N ∞ / N 9 / 5 0 / 5 8 / 5 ∞ / N 14 / 5 ∞ / N 6 9
1 11 7
G (6) ∞ / N ∞ / N ∞ / N 7 / 6 ∞ / N 8 / 6 0 / 6 11 / 6 9 / 6 ∞ / N A D
H (7) ∞ / N ∞ / N ∞ / N 12 / 7 ∞ / N ∞ / N 11 / 7 0 / 7 9 / 7 6 / 7 2 5
4
12 H 6
J
I (8) ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N 14 / 8 9 / 8 9 / 8 0 / 8 7 / 8
J (9) ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N 6 / 9 7 / 9 0 / 9 B 3
C 164
 Example: k = 0 (A)
Consider path through vertex A:
We DO NOT update here.
• 𝐷 → 𝐶:
• 𝐷 → 𝐴 → 𝐶: 1 + 5 = 6 > 4 (NOT OK)

A (0) B (1) C (2) D (3) E (4) F (5) G (6) H (7) I (8) J (9)
A (0) 0/0 2/0 5/0 1/0 6/0 ∞/N ∞/N ∞/N ∞/N ∞/N
B (1) 2/1 0/1 3/1 3/0 8/0 ∞/N ∞/N ∞/N ∞/N ∞/N
C (2) 5 / 2 3 / 2 0 / 2 4 / 2 11 / 0 ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N F
9 14
D (3) 1/3 3/0 4 / 3 0 / 3 10 / 3 ∞ / N 7 / 3 12 / 3 ∞ / N ∞ / N 8
9
E (4) 6 / 4 ∞ / N ∞ / N 10 / 4 0 / 4 9 / 4 ∞ / N ∞ / N ∞ / N ∞ / N E G I
10 7
F (5) ∞ / N ∞ / N ∞ / N ∞ / N 9 / 5 0 / 5 8 / 5 ∞ / N 14 / 5 ∞ / N 6 9
1 11 7
G (6) ∞ / N ∞ / N ∞ / N 7 / 6 ∞ / N 8 / 6 0 / 6 11 / 6 9 / 6 ∞ / N A D
H (7) ∞ / N ∞ / N ∞ / N 12 / 7 ∞ / N ∞ / N 11 / 7 0 / 7 9 / 7 6 / 7 2 5
4
12 H 6
J
I (8) ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N 14 / 8 9 / 8 9 / 8 0 / 8 7 / 8
J (9) ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N 6 / 9 7 / 9 0 / 9 B 3
C 165
 Example: k = 0 (A)
Consider path through vertex A:
dist[3, 4] = dist[3, 0] + dist[0, 4] = 1 + 6 = 7
• 𝐷 → 𝐸:
prev[3, 4] = prev[0, 4] = 0
• 𝐷 → 𝐴 → 𝐸: 1 + 6 = 7 < 10 (OK)

A (0) B (1) C (2) D (3) E (4) F (5) G (6) H (7) I (8) J (9)
A (0) 0/0 2/0 5/0 1/0 6/0 ∞/N ∞/N ∞/N ∞/N ∞/N
B (1) 2/1 0/1 3/1 3/0 8/0 ∞/N ∞/N ∞/N ∞/N ∞/N
C (2) 5 / 2 3 / 2 0 / 2 4 / 2 11 / 0 ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N F
9 14
D (3) 1/3 3/0 4/3 0/3 7 / 0 ∞ / N 7 / 3 12 / 3 ∞ / N ∞ / N 8
9
E (4) 6 / 4 ∞ / N ∞ / N 10 / 4 0 / 4 9 / 4 ∞ / N ∞ / N ∞ / N ∞ / N E G I
10 7
F (5) ∞ / N ∞ / N ∞ / N ∞ / N 9 / 5 0 / 5 8 / 5 ∞ / N 14 / 5 ∞ / N 6 9
1 11 7
G (6) ∞ / N ∞ / N ∞ / N 7 / 6 ∞ / N 8 / 6 0 / 6 11 / 6 9 / 6 ∞ / N A D
H (7) ∞ / N ∞ / N ∞ / N 12 / 7 ∞ / N ∞ / N 11 / 7 0 / 7 9 / 7 6 / 7 2 5
4
12 H 6
J
I (8) ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N 14 / 8 9 / 8 9 / 8 0 / 8 7 / 8
J (9) ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N 6 / 9 7 / 9 0 / 9 B 3
C 166
 Example: k = 0 (A)
Consider path through vertex A:
dist[4, 1] = dist[4, 0] + dist[0, 1] = 6 + 2 = 8
• 𝐸 → 𝐵:
prev[4, 1] = prev[0, 1] = 0
• 𝐸 → 𝐴 → 𝐵: 6 + 2 = 8 < ∞ (OK)

A (0) B (1) C (2) D (3) E (4) F (5) G (6) H (7) I (8) J (9)
A (0) 0/0 2/0 5/0 1/0 6/0 ∞/N ∞/N ∞/N ∞/N ∞/N
B (1) 2/1 0/1 3/1 3/0 8/0 ∞/N ∞/N ∞/N ∞/N ∞/N
C (2) 5 / 2 3 / 2 0 / 2 4 / 2 11 / 0 ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N F
9 14
D (3) 1/3 3/0 4/3 0/3 7 / 0 ∞ / N 7 / 3 12 / 3 ∞ / N ∞ / N 8
9
E (4) 6/4 8 / 0 ∞ / N 10 / 4 0 / 4 9 / 4 ∞ / N ∞ / N ∞ / N ∞ / N E G I
10 7
F (5) ∞ / N ∞ / N ∞ / N ∞ / N 9 / 5 0 / 5 8 / 5 ∞ / N 14 / 5 ∞ / N 6 9
1 11 7
G (6) ∞ / N ∞ / N ∞ / N 7 / 6 ∞ / N 8 / 6 0 / 6 11 / 6 9 / 6 ∞ / N A D
H (7) ∞ / N ∞ / N ∞ / N 12 / 7 ∞ / N ∞ / N 11 / 7 0 / 7 9 / 7 6 / 7 2 5
4
12 H 6
J
I (8) ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N 14 / 8 9 / 8 9 / 8 0 / 8 7 / 8
J (9) ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N 6 / 9 7 / 9 0 / 9 B 3
C 167
 Example: k = 0 (A)
Consider path through vertex A:
dist[4, 2] = dist[4, 0] + dist[0, 2] = 6 + 5 = 11
• 𝐸 → 𝐶:
prev[4, 2] = prev[0, 2] = 0
• 𝐸 → 𝐴 → 𝐶: 6 + 5 = 11 < ∞ (OK)

A (0) B (1) C (2) D (3) E (4) F (5) G (6) H (7) I (8) J (9)
A (0) 0/0 2/0 5/0 1/0 6/0 ∞/N ∞/N ∞/N ∞/N ∞/N
B (1) 2/1 0/1 3/1 3/0 8/0 ∞/N ∞/N ∞/N ∞/N ∞/N
C (2) 5 / 2 3 / 2 0 / 2 4 / 2 11 / 0 ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N F
9 14
D (3) 1/3 3/0 4/3 0/3 7 / 0 ∞ / N 7 / 3 12 / 3 ∞ / N ∞ / N 8
9
E (4) 6/4 8 / 0 11 / 0 10 / 4 0 / 4 9 / 4 ∞ / N ∞ / N ∞ / N ∞ / N E G I
10 7
F (5) ∞ / N ∞ / N ∞ / N ∞ / N 9 / 5 0 / 5 8 / 5 ∞ / N 14 / 5 ∞ / N 6 9
1 11 7
G (6) ∞ / N ∞ / N ∞ / N 7 / 6 ∞ / N 8 / 6 0 / 6 11 / 6 9 / 6 ∞ / N A D
H (7) ∞ / N ∞ / N ∞ / N 12 / 7 ∞ / N ∞ / N 11 / 7 0 / 7 9 / 7 6 / 7 2 5
4
12 H 6
J
I (8) ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N 14 / 8 9 / 8 9 / 8 0 / 8 7 / 8
J (9) ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N 6 / 9 7 / 9 0 / 9 B 3
C 168
 Example: k = 0 (A)
Consider path through vertex A:
dist[3, 4] = dist[3, 0] + dist[0, 4] = 1 + 6 = 7
• 𝐸 → 𝐷:
prev[3, 4] = prev[0, 4] = 0
• 𝐸 → 𝐴 → 𝐷: 6 + 1 = 7 < 10 (OK)

A (0) B (1) C (2) D (3) E (4) F (5) G (6) H (7) I (8) J (9)
A (0) 0/0 2/0 5/0 1/0 6/0 ∞/N ∞/N ∞/N ∞/N ∞/N
B (1) 2/1 0/1 3/1 3/0 8/0 ∞/N ∞/N ∞/N ∞/N ∞/N
C (2) 5 / 2 3 / 2 0 / 2 4 / 2 11 / 0 ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N F
9 14
D (3) 1/3 3/0 4/3 0/3 7 / 0 ∞ / N 7 / 3 12 / 3 ∞ / N ∞ / N 8
9
E (4) 6/4 8 / 0 11 / 0 7 / 0 0/4 9/4 ∞/N ∞/N ∞/N ∞/N E G I
10 7
F (5) ∞ / N ∞ / N ∞ / N ∞ / N 9 / 5 0 / 5 8 / 5 ∞ / N 14 / 5 ∞ / N 6 9
1 11 7
G (6) ∞ / N ∞ / N ∞ / N 7 / 6 ∞ / N 8 / 6 0 / 6 11 / 6 9 / 6 ∞ / N A D
H (7) ∞ / N ∞ / N ∞ / N 12 / 7 ∞ / N ∞ / N 11 / 7 0 / 7 9 / 7 6 / 7 2 5
4
12 H 6
J
I (8) ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N 14 / 8 9 / 8 9 / 8 0 / 8 7 / 8
J (9) ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N 6 / 9 7 / 9 0 / 9 B 3
C 169
 Example: k = 0 (A)

Now you can see the state after updated.

A (0) B (1) C (2) D (3) E (4) F (5) G (6) H (7) I (8) J (9)
A (0) 0/0 2/0 5/0 1/0 6/0 ∞/N ∞/N ∞/N ∞/N ∞/N
B (1) 2/1 0/1 3/1 3/0 8/0 ∞/N ∞/N ∞/N ∞/N ∞/N
C (2) 5 / 2 3 / 2 0 / 2 4 / 2 11 / 0 ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N
F
9 14
D (3) 1/3 3/0 4/3 0/3 7 / 0 ∞ / N 7 / 3 12 / 3 ∞ / N ∞ / N 8
9
E (4) 6/4 8 / 0 11 / 0 7 / 0 0/4 9/4 ∞/N ∞/N ∞/N ∞/N E G I
10 7
F (5) ∞ / N ∞ / N ∞ / N 6 9
∞ / N 9 / 5 0 / 5 8 / 5 ∞ / N 14 / 5 ∞ / N 1 11 7
G (6) ∞ / N ∞ / N ∞ / N 7 / 6 ∞ / N 8 / 6 0 / 6 11 / 6 9 / 6 ∞ / N
A D
H (7) ∞ / N ∞ / N ∞ / N 12 / 7 ∞ / N ∞ / N 11 / 7 0 / 7 9 / 7 6 / 7 2
5
4
12 H 6
J
I (8) ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N 14 / 8 9 / 8 9 / 8 0 / 8 7 / 8
J (9) ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N ∞ / N 6 / 9 7 / 9 0 / 9 B 3
C 170
Example: k = 9 (J)
A (0) B (1) C (2) D (3) E (4) F (5) G (6) H (7) I (8) J (9)
A (0) 0 / 0 2 / 0 5 / 0 1 / 0 6 / 0 15 / 4 8 / 3 13 / 3 17 / 6 19 / 7
B (1) 2 / 1 0 / 1 3 / 1 3 / 0 8 / 0 17 / 4 10 / 3 15 / 3 19 / 6 21 / 7
C (2) 5 / 2 3 / 2 0 / 2 4 / 2 11 / 0 19 / 6 11 / 3 16 / 3 20 / 6 22 / 7
D (3) 1 / 3 3 / 0 4 / 3 0 / 3 7 / 0 15 / 6 7 / 3 12 / 3 16 / 6 18 / 7
E (4) 6 / 4 8 / 0 11 / 0 7 / 0 0 / 4 9 / 4 14 / 3 19 / 3 23 / 5 25 / 7
F (5) 15 / 4 17 / 0 19 / 3
F
15 / 6 9 / 5 0 / 5 8 / 5 19 / 6 14 / 5 21 / 8 14
9
G (6) 8 / 3 10 / 0 11 / 3 7 / 6 14 / 0 8 / 6 0 / 6 11 / 6 9 / 6 16 / 8 8
9
H (7) 13 / 3 15 / 0 16 / 3 12 / 7 19 / 0 19 / 6 11 / 7 0 / 7 9 / 7 6 / 7
E G I
10 7
6 9
I (8) 17 / 3 19 / 0 20 / 3 16 / 6 23 / 5 14 / 8 9 / 8 9 / 8 0 / 8 7 / 8 1 11 7
A D
J (9) 19 / 3 21 / 0 22 / 3 18 / 7 25 / 0 21 / 8 16 / 8 6 / 9 7 / 9 0 / 9
2
5
4
12 H 6
J
pred[8][1 (B)] = 0 (A); pred[8][0 (A)] = 3 (D);
pred[8][3 (D)] = 6 (G); pred[8][6 (G)] = 8 (I); B 3
C
I → G → D → A → B with distance 19 172
Correctness

Theorem. If there are no negative cycles in a weighted directed graph G, then

the Floyd-Warshall algorithm, running on G, returns a matrix 𝐷 (𝑛) so that
𝐷𝑛 𝑢, 𝑣 = distance between 𝑢 and 𝑣 in 𝐺

173
Running time complexity

• Running time: 𝑂 𝑛3
– Better than running BF 𝑛 times!

– Not really better than running Dijkstra 𝑛 times

• ut it’s simpler to implement and handles negative weights.

174
Complexity
1. Floyd_Warshall(G): //G is the graph, w(u,v): weight of edge (u,v)
2. N = number_of_vertices_in(G)
3. dist[N][N] ← ∞ // Distance matrix is initially infinite 𝑂 1
4. pred[N][N] ← NULL // No predecessor yet

5. for all vertices i:

6. for all vertices j:
7. dist[i, j] ← w(i, j) // Direct edge weight or ∞ (0 if i=j) 𝑂 𝑉2
8. pred[i, j] = i if dist[i, j] != ∞

9. // k - intermediate vertex, i - source vertex, j - destination vertex

10. for k ← 1 to V:
11. for all vertices i: 𝑂 𝑉3
12. for all vertices j: Total cost:
13. // Relaxation: Check if path i → k → j is shorter 𝑂(𝑉 3 )
14. if dist[i, k] != ∞ and dist[k, j] != ∞ and dist[i, k] + dist[k, j] < dist[i, j]:
15. dist[i, j] ← dist[i, k] + dist[k, j]
16. pred[i, j] ← pred[k, j]
Storage complexity

• Enough to hold two 𝑛-by-𝑛 arrays, and the original graph.

– As with Bellman-Ford, we don’t really need to store all 𝑛 of the
𝐷(𝑘)

176
What if there are negative cycles?

• Just like Bellman-Ford, Floyd-Warshall can detect negative cycles.

• If there is a negative cycle, then there is a path from v to v that goes
through all n vertices that has cost < 0.
– That’s just the definition of a negative cycle.

• So 𝐷 𝑛 𝑣, 𝑣 < 0
• So check for that at the end.
– if there is such a v, return negative cycle.

177
Q&A

178