Graph theory

Routing problem

[Link]
Chapter 4: Shortest Path Problem
• Introduction to the shortest path problem
• Dijkstra
• Bellman-Ford Algorithm
• Floyd- Warshall algorithm
 Problem Statement
• The routing problem is a central challenge in many graph theory applications.
• Representing networks such as routes, Internet connections, or social
interactions.
• The goals is to minimize some metric, such as distance, time, or cost.
• Routing problems apply to both directed and undirected graphs.
• This is crucial in a variety of areas:
• Transportation networks: Minimize the distance or travel time between two points.
• Telecommunications and computer networks: Optimizing bandwidth usage and
reducing transmission delays.
• Logistics and distribution: Finding optimal routes for transporting goods while
minimizing costs.
The Shortest Path Problem 3
 Problem Statement
• Let G=(V,E) be a graph where:
• Each edge 𝒆 ∈ 𝑬 may have an associated weight w(e), representing a cost
metric such as distance, time, or expense.
• The weights may be non-negative or, in some cases, include negative values,
depending on the application.
• The routing problem involves finding a path or a set of paths 𝑃 =
𝑣1 , 𝑣2 , … , 𝑣𝑘 ∈ 𝐺 that connects a source node 𝑠 ∈ 𝑉 to a destination node
𝑡 ∈ 𝑉, such that a specified objective function is minimized.
• The objective function typically minimizes the path cost: The sum of edge
weights along the path, σ 𝑒∈𝑃 𝑤(𝑒).

The Shortest Path Problem 3

 Problem Statement
• there are indeed three main types of shortest path problems :
[Link] Path Between Two Specific Vertices: Finding the shortest path from
vertex i to vertex j.
[Link] Path from a Single Vertex to All Other Vertices: Finding the
shortest paths from a single source vertex i to all other vertices in the graph.
• Common algorithms for the first and second problem include:
• Dijkstra’s Algorithm (for non-negative edge weights)
• Bellman-Ford Algorithm (handles negative weights and detects negative cycles)
[Link] Paths Between All Pairs of Vertices: Finding the shortest paths bet
ween every pair of vertices in the graph.
• The Floyd-Warshall algorithm is specifically designed for this problem.
The Shortest Path Problem 3
Dijkstra's algorithm
• The algorithm due to Dijkstra is based on the following principle: If
the shortest path connecting E to S passes through the vertices S 1 , S
2 , …, S k then, the different steps are also the shortest paths
connecting E to the different vertices S 1 , S 2 , …, S k .
• We construct the desired path step by step by choosing at each
iteration of the algorithm, a vertex S i of the graph among those which
have not yet been processed, such that the provisionally known
length of the shortest path going from E to S i is the shortest possible.
 Dijkstra’s Algorithm
• Initialization of the algorithm:
• Set the weight (distance) of the source vertex to 0.
• Assign a temporary weight of ∞ to all other vertices.
• Repeat the following operations until all vertices have definitive weights (shortest distances) from the source.
• Select the Vertex with Minimum Weight:
• Among vertices with temporary weights, choose the vertex 𝑋 that has the minimum weight w(𝑋).
• Fix 𝑋 by marking it as permanently assigned the weight w(𝑋).
• Update Adjacent Vertices:
• For each unmarked vertex Y adjacent to the recently fixed vertex X :
• Calculate the tentative weight s, which is the sum of the weight of x (i.e., w(X)) and the weight of the
edge connecting X to Y.
• If s is less than Y 's current temporary weight, update Y's weight to s and note X as the predecessor of Y
(to trace the path back to the source).
• When the vertex is finally marked
• The shortest path from Source to Destination is obtained by writing the path from left to right starting from
the end.
 8
b e
3 5

5 2
a d
g

4 7
c f
3
 8
b e
3 5

5 2
a d
g
a b c d e f g
4 7
c f
3
 8
b e
3 5

5 2
a d
g
a b c d e f g
0 ∞ ∞ ∞ ∞ ∞ ∞ 4 7
c f
3
 8
b e
3 5

5 2
a d
g
a b c d e f g
0 ∞ ∞ ∞ ∞ ∞ ∞ a(0) 4 7
c f
3
 8
b e
3 5

5 2
a d
g
a b c d e f g
0 ∞ ∞ ∞ ∞ ∞ ∞ a(0) 4 7
c f
3
a(3) a(4) a(5) ∞ ∞ ∞
 8
b e
3 5

5 2
a d
g
a b c d e f g
0 ∞ ∞ ∞ ∞ ∞ ∞ a(0) 4 7
c f
3
a(3)
∞ a(4)
∞ a(5)
∞ ∞ ∞ ∞
 8
b e
3 5

5 2
a d
g
a b c d e f g
0 ∞ ∞ ∞ ∞ ∞ ∞ a(0) 4 7
c f
3
a(3)
∞ a(4)
∞ a(5)
∞ ∞ ∞ ∞
 8
b e
3 5

5 2
a d
g
a b c d e f g
0 ∞ ∞ ∞ ∞ ∞ ∞ a(0) 4 7
c f
3
a(3)
∞ a(4)
∞ a(5)
∞ ∞ ∞ ∞ b(3)
 8
b e
3 5

5 2
a d
g
a b c d e f g
0 ∞ ∞ ∞ ∞ ∞ ∞ a(0) 4 7
c f
3
a(3)
∞ a(4)
∞ a(5)
∞ ∞ ∞ ∞ b(3)
a(4) a(5) ∞ ∞ ∞
 8
b e
3 5

5 2
a d
g
a b c d e f g
0 ∞ ∞ ∞ ∞ ∞ ∞ a(0) 4 7
c f
3
a(3)
∞ a(4)
∞ a(5)
∞ ∞ ∞ ∞ b(3)
a(4) a(5) ∞
B(3+8) ∞ ∞
 8
b e
3 5

5 2
a d
g
a b c d e f g
0 ∞ ∞ ∞ ∞ ∞ ∞ a(0) 4 7
c f
3
a(3)
∞ a(4)
∞ a(5)
∞ ∞ ∞ ∞ b(3)
a(4) a(5) ∞
b(11)
B(3+8) ∞ ∞
 8
b e
3 5

5 2
a d
g
a b c d e f g
0 ∞ ∞ ∞ ∞ ∞ ∞ a(0) 4 7
c f
3
a(3)
∞ a(4)
∞ a(5)
∞ ∞ ∞ ∞ b(3)
a(4) a(5) ∞
b(11)
B(3+8) ∞ ∞ c(4)
 8
b e
3 5

5 2
a d
g
a b c d e f g
0 ∞ ∞ ∞ ∞ ∞ ∞ a(0) 4 7
c f
3
a(3)
∞ a(4)
∞ a(5)
∞ ∞ ∞ ∞ b(3)
a(4) a(5) ∞
b(11)
B(3+8) ∞ ∞ c(4)
a(5) b(11) ∞ ∞
 8
b e
3 5

5 2
a d
g
a b c d e f g
0 ∞ ∞ ∞ ∞ ∞ ∞ a(0) 4 7
c f
3
a(3)
∞ a(4)
∞ a(5)
∞ ∞ ∞ ∞ b(3)
a(4) a(5) ∞
b(11)
B(3+8) ∞ ∞ c(4)
a(5) b(11) C(3+4)
∞ ∞
 8
b e
3 5

5 2
a d
g
a b c d e f g
0 ∞ ∞ ∞ ∞ ∞ ∞ a(0) 4 7
c f
3
a(3)
∞ a(4)
∞ a(5)
∞ ∞ ∞ ∞ b(3)
a(4) a(5) ∞
b(11)
B(3+8) ∞ ∞ c(4)
a(5) C(7)
b(11) C(3+4)
∞ ∞
 8
b e
3 5

5 2
a d
g
a b c d e f g
0 ∞ ∞ ∞ ∞ ∞ ∞ a(0) 4 7
c f
3
a(3)
∞ a(4)
∞ a(5)
∞ ∞ ∞ ∞ b(3)
a(4) a(5) ∞
b(11)
B(3+8) ∞ ∞ c(4)
a(5) C(7)
b(11) C(3+4)
∞ ∞ d(5)
b(11) C(7) ∞
 8
b e
3 5

5 2
a d
g
a b c d e f g
0 ∞ ∞ ∞ ∞ ∞ ∞ a(0) 4 7
c f
3
a(3)
∞ a(4)
∞ a(5)
∞ ∞ ∞ ∞ b(3)
a(4) a(5) ∞
b(11)
B(3+8) ∞ ∞ c(4)
a(5) C(7)
b(11) C(3+4)
∞ ∞ d(5)
b(11)
d(7) C(7) ∞
 8
b e
3 5

5 2
a d
g
a b c d e f g
0 ∞ ∞ ∞ ∞ ∞ ∞ a(0) 4 7
c f
3
a(3)
∞ a(4)
∞ a(5)
∞ ∞ ∞ ∞ b(3)
a(4) a(5) ∞
b(11)
B(3+8) ∞ ∞ c(4)
a(5) C(7)
b(11) C(3+4)
∞ ∞ d(5)
b(11)
d(7) C(7) ∞ f(7)
 8
b e
3 5

5 2
a d
g
a b c d e f g
0 ∞ ∞ ∞ ∞ ∞ ∞ a(0) 4 7
c f
3
a(3)
∞ a(4)
∞ a(5)
∞ ∞ ∞ ∞ b(3)
a(4) a(5) ∞
b(11)
B(3+8) ∞ ∞ c(4)
a(5) C(7)
b(11) C(3+4)
∞ ∞ d(5)
b(11)
d(7) C(7) ∞ f(7)
d(7) ∞
 8
b e
3 5

5 2
a d
g
a b c d e f g
0 ∞ ∞ ∞ ∞ ∞ ∞ a(0) 4 7
c f
3
a(3)
∞ a(4)
∞ a(5)
∞ ∞ ∞ ∞ b(3)
a(4) a(5) ∞
b(11)
B(3+8) ∞ ∞ c(4)
a(5) C(7)
b(11) C(3+4)
∞ ∞ d(5)
b(11)
d(7) C(7) ∞ f(7)
d(7) ∞
f(14)
 8
b e
3 5

5 2
a d
g
a b c d e f g
0 ∞ ∞ ∞ ∞ ∞ ∞ a(0) 4 7
c f
3
a(3)
∞ a(4)
∞ a(5)
∞ ∞ ∞ ∞ b(3)
a(4) a(5) ∞
b(11)
B(3+8) ∞ ∞ c(4)
a(5) C(7)
b(11) C(3+4)
∞ ∞ d(5)
b(11)
d(7) C(7) ∞ f(7)
d(7) ∞
f(14) e(7)
 8
b e
3 5

5 2
a d
g
a b c d e f g
0 ∞ ∞ ∞ ∞ ∞ ∞ a(0) 4 7
c f
3
a(3)
∞ a(4)
∞ a(5)
∞ ∞ ∞ ∞ b(3)
a(4) a(5) ∞
b(11)
B(3+8) ∞ ∞ c(4)
a(5) C(7)
b(11) C(3+4)
∞ ∞ d(5)
b(11)
d(7) C(7) ∞ f(7)
d(7) ∞
F(7+7)
f(14) e(7)
f(14)
 8
b e
3 5

5 2
a d
g
a b c d e f g
0 ∞ ∞ ∞ ∞ ∞ ∞ a(0) 4 7
c f
3
a(3)
∞ a(4)
∞ a(5)
∞ ∞ ∞ ∞ b(3)
a(4) a(5) ∞
b(11)
B(3+8) ∞ ∞ c(4)
a(5) C(7)
b(11) C(3+4)
∞ ∞ d(5)
b(11)
d(7) C(7) ∞ f(7)
d(7) ∞
F(7+7)
f(14) e(7)
f(14)
e(12)
 8
b e
3 5

5 2
a d
g
a b c d e f g
0 ∞ ∞ ∞ ∞ ∞ ∞ a(0) 4 7
c f
3
a(3)
∞ a(4)
∞ a(5)
∞ ∞ ∞ ∞ b(3)
a(4) a(5) ∞
b(11)
B(3+8) ∞ ∞ c(4)
a(5) C(7)
b(11) C(3+4)
∞ ∞ d(5)
b(11)
d(7) C(7) ∞ f(7)
d(7) ∞
F(7+7)
f(14) e(7)
f(14)
e(12) g(12)
Example

b
3 1

a d
5
-2
c
Example
a b c d
0 ∞ ∞ ∞ a(0) b
3 1

a d
5
-2
c
Example
a b c d
0 ∞ ∞ ∞ a(0) b
1
a (3) a(5) ∞ b(3) 3

a d
5
-2
c
Example
a b c d
0 ∞ ∞ ∞ a(0) b
1
a (3) a(5) ∞ b(3) 3

a(5) b(4) d(4) a d

5
-2
c
Example
a b c d
0 ∞ ∞ ∞ a(0) b
1
a (3) a(5) ∞ b(3) 3

a(5) b(4) d(4) a d

a(5) c(5)
5
-2
c
 Example
a b c d
0 ∞ ∞ ∞ a(0) b
1
a (3) a(5) ∞ b(3) 3

a(5) b(4) d(4) a d

a(5) c(5)
5
-2
c

• The shortest path between a and d calculated by Dijkstra's algorithm is 4

while there is a shorter one via "c" which is 3 .
 Bellman-Ford algorithm (1958-1962)
• The presence of edge weights with different signs allows the modeling of
complex situations with variable costs and variable profits.
• Dijkstra's algorithm does not allow negative edges to be considered, because
once a vertex is labeled, this label cannot be changed in subsequent
iterations.
• Dijkstra's algorithm is therefore called label-fixing.
• The Bellman-Ford algorithm, on the other hand, allows a label that is not final
until the algorithm completes (the label is changed iteratively).
• This type of algorithm is called label-correcting.
 Bellman-Ford algorithm (1958-1962)
Bellman-Ford Procedure
Input: Graph G = (V, E) , Edge Lengths L( u,v ) , and S a source vertex
Output: dist ( distance) and pred (predecessor) two arrays containing the
shortest path between the source S and each vertex
{
// Step 1: initialize graph
for all u in V Do
{
dist (u) = ∞;
prev (u) = nil ;
}
dist (S) = 0;
// Step 2: relax edges repeatedly
for i = 1 to |V|-1 Do {
for all Edge (u, v) in E Do
Dist (v) = min{ dist (v), dist (u) + L( u,v )
}
// Step 3: check for negative-weight cycles
for All edge (u, v) in E do
if dist (u) + L( u,v ) < dist (v) then
{
A negative cycle exists; find a vertex on the cycle;
Break;
}
}
 C
2
-1

2
A E
2
-4
2 D

-2
5 vertices 4 iterations for calculating the shortest path B

An iteration to check if there is an improving circuit

Initialization C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B ∞ -
C ∞ -
D ∞ -
E ∞ -
iteration 1 of 4 Arc(A, C) C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B ∞ -
C ∞ -
D ∞ -
E ∞ -
iteration 1 of 4 Arc(A, C) C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B ∞ -
Dist (C) = min( Dist (C), Dist (A) + L(A, C))
C ∞ -
D ∞ - Dist (C) = min(∞, 0+ (-1) )

E ∞ -
iteration 1 of 4 Arc(A, C) C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B ∞ -
Dist (C) = min( Dist (C), Dist (A) + L(A, C))
C -1 A
D ∞ - Dist (C) = -1

E ∞ -
iteration 1 of 4 Arc(A, B) C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B ∞ -
C -1 A
D ∞ -
E ∞ -
iteration 1 of 4 Arc(A, B) C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B ∞ -
Dist (B) = min( Dist (B), Dist (A) + L(A, B))
C -1 A
D ∞ - Dist (B) = min(∞, 0+ 2 )

E ∞ -
iteration 1 of 4 Arc(A, B) C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B 2 A
Dist (B) = min( Dist (B), Dist (A) + L(A, B))
C -1 A
D ∞ - Dist (B) = 2

E ∞ -
iteration 1 of 4 Arc(C, B) C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B 2 A
Dist (B) = min( Dist (B), Dist (C) + L(C, B))
C -1 A
D ∞ - Dist (B) = min(2, 2 + (-1) ) = 1

E ∞ -
iteration 1 of 4 Arc(C, B) C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B 1 C
Dist (B) = min( Dist (B), Dist (C) + L(C, B))
C -1 A
D ∞ - Dist (B) = 1

E ∞ -
iteration 1 of 4 Arc(B, D) C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B 1 C
Dist (D) = min( Dist (D), Dist (B) + L(B, D))
C -1 A
D ∞ - Dist (D) = min(∞, 1+ (-2) )

E ∞ -
iteration 1 of 4 Arc(B, D) C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B 1 C
Dist (D) = min( Dist (D), Dist (B) + L(B, D))
C -1 A
D -1 B Dist (D) = -1

E ∞ -
iteration 1 of 4 Arc(C, E) C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B 1 C
Dist (E) = min( Dist (E), Dist (C) + L(C, E))
C -1 A
D -1 B Dist (E) = min(∞, -1+ (2) ) = 1

E ∞ -
iteration 1 of 4 Arc(C, E) C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B 1 C
Dist (E) = min( Dist (E), Dist (C) + L(C, E))
C -1 A
D -1 B Dist (E) = min(∞, -1+ (2) ) = 1

E ∞ -
iteration 1 of 4 Arc(C, E) C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B 1 C
Dist (E) = min( Dist (E), Dist (C) + L(C, E))
C -1 A
D -1 B Dist (E) = min(∞, -1+ (2) ) = 1

E 1 C
iteration 1 of 4 Arc(D, E) C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B 1 C
Dist (E) = min( Dist (E), Dist (D) + L(D, E))
C -1 A
D -1 B Dist (E) = min(-1, -1+ (-4) ) = -5

E 1 C
iteration 1 of 4 Arc(D, E) C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B 1 C
Dist (E) = min( Dist (E), Dist (D) + L(D, E))
C -1 A
D -1 B Dist (E) = -5

E -5 D
iteration 1 of 4 Arc(C, D) C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B 1 C
Dist (D) = min( Dist (D), Dist (C) + L(C, D))
C -1 A
D -1 B Dist (D) = min(-1, 1 + 2) = -1

E -5 D
iteration 2 of 4 C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B 1 C
C -1 A
D -1 B
E -5 D
iteration 2 of 4 Arc(A, B) C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B 1 C
C -1 A Dist (B) = min(1, 0 + 2) = 2
D -1 B
E -5 D
iteration 2 of 4 Arc(A, C) C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B 1 C
C -1 A Dist (C) = min(-1, 0 + (-1)) = -1
D -1 B
E -5 D
iteration 2 of 4 Arc(B, D) C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B 1 C
C -1 A Dist (D) = min(-1, 1 + (-2)) = -1
D -1 B
E -5 D
iteration 2 of 4 Arc(C, B) C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B 1 C
C -1 A Dist (B) = min(1, -1 + (2)) = 1
D -1 B
E -5 D
iteration 2 of 4 Arc(C, D) C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B 1 C
C -1 A Dist (D) = min(-1, 1 + (2)) = -1
D -1 B
E -5 D
iteration 2 of 4 Arc(C, E) C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B 1 C
C -1 A Dist (E) = min(-1, 1 + (2)) = -1
D -1 B
E -5 D
iteration 2 of 4 Arc(D, E) C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B 1 C
C -1 A Dist (D) = min(-1, -1 + (-4)) = -5
D -1 B
E -5 D
iteration 2 of 4 Arc(D, E) C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B 1 C
C -1 A Dist (D) = min(-1, -1 + (-4)) = -5
D -1 B
E -5 D
iteration 2 of 4 C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B 1 C
C -1 A
D -1 B
E -5 D
iteration 3 of 4 C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B 1 C
C -1 A
D -1 B
E -5 D
iteration 4 of 4 C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B 1 C
C -1 A
D -1 B
E -5 D
 Detection of negative circuits C
2
-1

2
A E
2
Dist -4
2 D

A 0 -2
B

B 1
C -1 If Dist (U) > min( Dist (U), Dist (U) + L(U, V) ) Then
the graph contains a negative circuit
D -1
E -5
 Detection of negative circuits C
2
-1

2
A E
2
Dist -4
2 D

A 0 -2
B

Arc(A, B)
B 1
C -1 Dist (U) > min( Dist (U), Dist (U) + L(U, V) )
D -1
Dist (B) = 1 < min(1, 0 + 2) = 2
E -5
 Detection of negative circuits C
2
-1

2
A E
2
Dist -4
2 D

A 0 -2
B

Arc(A, C)
B 1
C -1 Dist (C) = -1 <= min( -1, 0 + (-1) ) = -1
D -1
E -5
 Detection of negative circuits C
2
-1

2
A E
2
Dist -4
2 D

A 0 -2
B

Arc(B, D)
B 1
C -1 Dist (D) =-1 <= min(-1, 1 + (-2)) = -1
D -1
E -5
 Detection of negative circuits C
2
-1

2
A E
2
Dist -4
2 D

A 0 -2
B

Arc(C, B)
B 1
C -1 Dist (B) = 1 <= min(1, -1 + (2)) = 1
D -1
E -5
 Detection of negative circuits C
2
-1

2
A E
2
Dist -4
2 D

A 0 -2
B

Arc(C, D)
B 1
C -1 Dist (D) = -1 <= min( -1, 1 + (2) ) = -1
D -1
E -5
 Detection of negative circuits C
2
-1

2
A E
2
Dist -4
2 D

A 0 -2
B

Arc(C, E)
B 1
C -1 Dist (E) = -5 <= min( -1, 1 + (2) ) = -1
D -1
E -5
 Detection of negative circuits C
2
-1

2
A E
2
Dist -4
2 D

A 0 -2
B

Arc(D, E)
B 1
C -1 Dist (D) = -1 <= min(-1, -1 + (-4)) = -5
D -1
E -5
 Detection of negative circuits C
2
-1

2
A E
2
Dist -4
2 D

A 0 -2
B

Arc(D, E)
B 1
C -1 Dist (D) = -1 <= min(-1, -1 + (-4)) = -5
D -1
E -5
END C
2
-1

2
A E
2
Dist Prev -4
2 D

A 0 - -2
B

B 1 C
C -1 A • Absence of negative weight circuit accessible from
vertex “A” .
D -1 B • The result represents the shortest paths from "A" to
all other vertices of the graph as well as their weights.
E -5 D
Exercise 1
• Calculate the shortest path from A to the other points of the graph using
the Bellman-Ford algorithm.

b
3 1

a d
5
-2
c
Improving cycle
• Improving cycles (or negative cycles in English) are infinite loops that
continuously reduce the total path distance.

• They pose a real problem because each pass through the cycle can
further reduce the distance, always yielding a “better” path to take.

• When a graph contains this type of cycle, there is no solution due to

this infinite loop, so detecting it becomes essential.
 5
A B

4 -6 3

C D
2
 5
A B

Dist Prev 4 -6 3
A 0 - C D

B ∞ - 2

C ∞ -
D ∞ -
iteration 1 of 3
5
A B

Dist Prev 4 -6 3
A 0 - C D

B ∞ - 2

C ∞ -
D ∞ -
iteration 1 of 3
5
A B

Dist Prev 4 -6 3
A 0 - C D

B 5 A 2

C ∞ -
D ∞ -
iteration 1 of 3
5
A B

Dist Prev 4 -6 3
A 0 - C D

B 5 A 2

C ∞ -
D ∞ -
iteration 1 of 3
5
A B

Dist Prev 4 -6 3
A 0 - C D

B 5 A 2

C 4 A
D ∞ -
iteration 1 of 3
5
A B

Dist Prev 4 -6 3
A 0 - C D

B 5 A 2

C 4 A
D ∞ -
iteration 1 of 3
5
A B

Dist Prev 4 -6 3
A 0 - C D

B 5 A 2

C 4 A
D 8 B
iteration 1 of 3
5
A B

Dist Prev 4 -6 3
A 0 - C D

B 5 A 2

C 4 A
D 8 B
iteration 1 of 3
5
A B

Dist Prev 4 -6 3
A 0 - C D

B -2 C 2

C 4 A
D 8 B
iteration 1 of 3
5
A B

Dist Prev 4 -6 3
A 0 - C D

B -2 C 2

C 4 A
D 8 B
iteration 2 of 3
5
A B

Dist Prev 4 -6 3
A 0 - C D

B -2 C 2

C 4 A
D 8 B
iteration 2 of 3
5
A B

Dist Prev 4 -6 3
A 0 - C D

B -2 C 2

C 4 A
D 8 B
iteration 2 of 3
5
A B

Dist Prev 4 -6 3
A 0 - C D

B -2 C 2

C 4 A
D 8 B
iteration 2 of 3
5
A B

Dist Prev 4 -6 3
A 0 - C D

B -2 C 2

C 4 A
D 1 B
iteration 2 of 3
5
A B

Dist Prev 4 -6 3
A 0 - C D

B -2 C 2

C 4 A
D 1 B
iteration 2 of 3
5
A B

Dist Prev 4 -6 3
A 0 - C D

B -2 C 2

C 4 A
D 1 B
iteration 2 of 3
5
A B

Dist Prev 4 -6 3
A 0 - C D

B -2 C 2

C 3 D
D 1 B
iteration 2 of 3
5
A B

Dist Prev 4 -6 3
A 0 - C D

B -2 C 2

C 3 D
D 1 B
iteration 3 of 3
5
A B

Dist Prev 4 -6 3
A 0 - C D

B -2 C 2

C 3 D
D 1 B
iteration 3 of 3
5
A B

Dist Prev 4 -6 3
A 0 - C D

B -2 C 2

C 3 D
D 1 B
iteration 3 of 3
5
A B

Dist Prev 4 -6 3
A 0 - C D

B -2 C 2

C 3 D
D 1 B
iteration 3 of 3
5
A B

Dist Prev 4 -6 3
A 0 - C D

B -2 C 2

C 3 D
D 1 B
iteration 3 of 3
5
A B

Dist Prev 4 -6 3
A 0 - C D

B -3 C 2

C 3 D
D 1 B
iteration 3 of 3
5
A B

Dist Prev 4 -6 3
A 0 - C D

B -3 C 2

C 3 D
D 1 B
 Detection of negative circuits
5
A B

Dist 4 -6 3
A 0 C D

B -3 2

C 3 Dist (U) > min( Dist (U), Dist (U) + L(U, V)

)
D 1
 Detection of negative circuits
5
A B

Dist 4 -6 3
A 0 C D

B -3 2

C 3 Dist (U) > min( Dist (U), Dist (U) + L(U, V)

)
D 1
 Detection of negative circuits
5
A B

Dist 4 -6 3
A 0 C D

B -3 2

C 3 Dist (U) > min( Dist (U), Dist (U) + L(U, V)

)
D 1
Dist (D) = 1 > min(1, -3 + 3) = 0
 Detection of negative circuits
5
A B

Dist 4 -6 3
A 0 C D

B -3 2

C 3 Dist (U) > min( Dist (U), Dist (U) + L(U, V)

)
D 1
Dist (D) = 1 > min(1, -3 + 3) = 0
Presence of negative circuits
Shortest path search algorithms

• Dijkstra Shortest path from one vertex to all other vertices, positive
arc weight > 0
• Bellman-Ford Shortest path from one vertex to all other vertices,
negative weight arc < 0
• Floyd- Warshall Shortest path between any pair of vertices
 Floyd- Warshall algorithm
• Allows to calculate the shortest path for any pair (X,Y) of vertices of the graph,
• the labels are no longer an array (one label per vertex), but a matrix M of size n*n
where the entry M ij corresponds to the shortest path between vertices i and j .
• This algorithm is valid regardless of the weights of the arcs, including if it involves
negative circuits (the algorithm allows us to prove the existence or non-existence of
such circuits).
• The algorithm consists of N main iterations; for each iteration K, we compute the
shortest paths between any pair of vertices with intermediate vertices belonging only
to the set {1,2,…K}.
• At initialization, we calculate the shortest path between any pair of vertices that have
no intermediate vertices, so we just take the length of the arcs that exist and put an
infinite weight if the arc does not exist.
𝐾
• Subsequently, if we note 𝑀𝑖𝑗 the value of the shortest path from i to j whose only
intermediate vertices are in the set {1,2,…K}, then we have the following equality:
𝑘 𝑘−1 𝑘−1 𝑘−1
𝑀𝑖𝑗 = min(𝑀𝑖𝑗 , 𝑀𝑖𝑘 +𝑀𝑘𝑗 )
 5
A B
initialization
4 -6 3

C D
2

M P
A B C D A B C D
A 0 ∞ ∞ ∞ A A 0 0 0
B ∞ 0 ∞ ∞ B 0 B 0 0
C ∞ ∞ 0 ∞ C 0 0 C 0
D ∞ ∞ ∞ 0 D 0 0 0 D
 5
A B
initialization
4 -6 3

C D
2

M P
A B C D A B C D
A 0 ∞ ∞ ∞ A A 0 0 0
B ∞ 0 ∞ ∞ B 0 B 0 0
C ∞ ∞ 0 ∞ C 0 0 C 0
D ∞ ∞ ∞ 0 D 0 0 0 D
 5
A B
initialization
4 -6 3

C D
2

M P
A B C D A B C D
A 0 5 4 ∞ A A A A 0
B ∞ 0 ∞ ∞ B 0 B 0 0
C ∞ ∞ 0 ∞ C 0 0 C 0
D ∞ ∞ ∞ 0 D 0 0 0 D
 5
A B
initialization
4 -6 3

C D
2

M P
A B C D A B C D
A 0 5 4 ∞ A A A A 0
B ∞ 0 ∞ ∞ B 0 B 0 0
C ∞ ∞ 0 ∞ C 0 0 C 0
D ∞ ∞ ∞ 0 D 0 0 0 D
 5
A B
initialization
4 -6 3

C D
2

M P
A B C D A B C D
A 0 5 4 ∞ A A A A 0
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ ∞ 0 ∞ C 0 0 C 0
D ∞ ∞ ∞ 0 D 0 0 0 D
 5
A B
initialization
4 -6 3

C D
2

M P
A B C D A B C D
A 0 5 4 ∞ A A A A 0
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 ∞ C 0 C C 0
D ∞ ∞ ∞ 0 D 0 0 0 D
 5
A B
initialization
4 -6 3

C D
2

M P
A B C D A B C D
A 0 5 4 ∞ A A A A 0
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 ∞ C 0 C C 0
D ∞ ∞ 2 0 D 0 0 D D
 K=1 5
A B
i=1

j=1 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] 0 > 0 + 0 2

M P
A B C D A B C D
A 0 5 4 ∞ A A A A 0
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 ∞ C 0 C C 0
D ∞ ∞ 2 0 D 0 0 D D
 K=2 5
A B
i=1

j=1 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] 0 > 5 + ∞ 2

M P
A B C D A B C D
A 0 5 4 ∞ A A A A 0
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 ∞ C 0 C C 0
D ∞ ∞ 2 0 D 0 0 D D
 K=2 5
A B
i=1

j=2 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] 5 > 5 + ∞ 2

M P
A B C D A B C D
A 0 5 4 ∞ A A A A 0
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 ∞ C 0 C C 0
D ∞ ∞ 2 0 D 0 0 D D
 K=2 5
A B
i=1

j=3 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] 4>5+∞ 2

M P
A B C D A B C D
A 0 5 4 ∞ A A A A 0
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 ∞ C 0 C C 0
D ∞ ∞ 2 0 D 0 0 D D
 K=2 5
A B
i=1

j=4 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] ∞>5+3 2

M P
A B C D A B C D
A 0 5 4 ∞ A A A A 0
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 ∞ C 0 C C 0
D ∞ ∞ 2 0 D 0 0 D D
 K=2 5
A B
i=1

j=4 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] ∞>8 2

M P
A B C D A B C D
A 0 5 4 8 A A A A B
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 ∞ C 0 C C 0
D ∞ ∞ 2 0 D 0 0 D D
 K=2 5
A B
i=2

j=1 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] ∞>0+∞ 2

M P
A B C D A B C D
A 0 5 4 8 A A A A B
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 ∞ C 0 C C 0
D ∞ ∞ 2 0 D 0 0 D D
 K=2 5
A B
i=2

j=2 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] 0>0+0 2

M P
A B C D A B C D
A 0 5 4 8 A A A A B
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 ∞ C 0 C C 0
D ∞ ∞ 2 0 D 0 0 D D
 K=2 5
A B
i=2

j=3 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] ∞>0+∞ 2

M P
A B C D A B C D
A 0 5 4 8 A A A A B
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 ∞ C 0 C C 0
D ∞ ∞ 2 0 D 0 0 D D
 K=2 5
A B
i=2

j=4 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] 3>0+3 2

M P
A B C D A B C D
A 0 5 4 8 A A A A B
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 ∞ C 0 C C 0
D ∞ ∞ 2 0 D 0 0 D D
 K=2 5
A B
i=3

j=1 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] ∞ > -6 + ∞ 2

M P
A B C D A B C D
A 0 5 4 8 A A A A B
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 ∞ C 0 C C 0
D ∞ ∞ 2 0 D 0 0 D D
 K=2 5
A B
i=3

j=2 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] -6 > -6 + 0 2

M P
A B C D A B C D
A 0 5 4 8 A A A A B
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 ∞ C 0 C C 0
D ∞ ∞ 2 0 D 0 0 D D
 K=2 5
A B
i=3

j=3 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] 0 > -6 + ∞ 2

M P
A B C D A B C D
A 0 5 4 8 A A A A B
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 ∞ C 0 C C 0
D ∞ ∞ 2 0 D 0 0 D D
 K=2 5
A B
i=3

j=4 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] ∞ > -6 + 3 2

M P
A B C D A B C D
A 0 5 4 8 A A A A B
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 ∞ C 0 C C 0
D ∞ ∞ 2 0 D 0 0 D D
 K=2 5
A B
i=3

j=4 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] ∞>-3 2

M P
A B C D A B C D
A 0 5 4 8 A A A A B
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 -3 C 0 C C B
D ∞ ∞ 2 0 D 0 0 D D
 K=2 5
A B
i=4

j=1 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] ∞ > ∞ + ∞ 2

M P
A B C D A B C D
A 0 5 4 8 A A A A B
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 -3 C 0 C C B
D ∞ ∞ 2 0 D 0 0 D D
 K=2 5
A B
i=4

j=2 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] ∞>∞+0 2

M P
A B C D A B C D
A 0 5 4 8 A A A A B
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 -3 C 0 C C B
D ∞ ∞ 2 0 D 0 0 D D
 K=2 5
A B
i=4

j=3 4 -6 3

M[ i , j] > M[ i , k]+ M[k, C

2
D
M[ i , j] > M[ i , k]+ M[k, j] 2>∞+0
j]
M P
A B C D A B C D
A 0 5 4 8 A A A A B
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 -3 C 0 C C B
D ∞ ∞ 2 0 D 0 0 D D
 K=2 5
A B
i=4

j=4 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] 0 > ∞ + 3 2

M P
A B C D A B C D
A 0 5 4 8 A A A A B
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 -3 C 0 C C B
D ∞ ∞ 2 0 D 0 0 D D
 K=3 5
A B
i=1

j=1 4 -6 3

M[ i , j] > M[ i , k]+ M[k, C

2
D
M[ i , j] > M[ i , k]+ M[k, j] 0 > 4 + ∞
j]
M P
A B C D A B C D
A 0 5 4 8 A A A A B
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 -3 C 0 C C B
D ∞ ∞ 2 0 D 0 0 D D
 K=3 5
A B
i=1

j=2 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] 5 > 4 + -6 2

M P
A B C D A B C D
A 0 5 4 8 A A A A B
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 -3 C 0 C C B
D ∞ ∞ 2 0 D 0 0 D D
 K=3 5
A B
i=1

j=2 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] 5 > -2 2

M P
A B C D A B C D
A 0 -2 4 8 A A C A B
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 -3 C 0 C C B
D ∞ ∞ 2 0 D 0 0 D D
 K=3 5
A B
i=1

j=3 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] 4>4+∞ 2

M P
A B C D A B C D
A 0 -2 4 8 A A C A B
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 -3 C 0 C C B
D ∞ ∞ 2 0 D 0 0 D D
 K=3 5
A B
i=1

j=4 4 -6 3

M[ i , j] > M[ i , k]+ M[k, C

2
D
M[ i , j] > M[ i , k]+ M[k, j] 8 > 4 + -3
j]
M P
A B C D A B C D
A 0 -2 4 8 A A C A B
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 -3 C 0 C C B
D ∞ ∞ 2 0 D 0 0 D D
 K=3 5
A B
i=1

j=4 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] 8>1 2

M P
A B C D A B C D
A 0 -2 4 1 A A C A C
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 -3 C 0 C C B
D ∞ ∞ 2 0 D 0 0 D D
 K=3 5
A B
i=1

j=4 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] 8 > 1 2

M P
A B C D A B C D
A 0 -2 4 1 A A C A C
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 -3 C 0 C C B
D ∞ ∞ 2 0 D 0 0 D D
 K=3 5
A B
i=1

j=4 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] 8>1 2

M P
A B C D A B C D
A 0 -2 4 1 A A C A C
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 -3 C 0 C C B
D ∞ ∞ 2 0 D 0 0 D D
 K=3 5
A B
i=2

j=1 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] ∞>∞+∞ 2

M P
A B C D A B C D
A 0 -2 4 1 A A C A C
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 -3 C 0 C C B
D ∞ ∞ 2 0 D 0 0 D D
 K=3 5
A B
i=2

j=2 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] 0>∞-6 2

M P
A B C D A B C D
A 0 -2 4 1 A A C A C
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 -3 C 0 C C B
D ∞ ∞ 2 0 D 0 0 D D
 K=3 5
A B
i=2

j=3 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] ∞ > ∞ - 6 2

M P
A B C D A B C D
A 0 -2 4 1 A A C A C
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 -3 C 0 C C B
D ∞ ∞ 2 0 D 0 0 D D
 K=3 5
A B
i=2

j=4 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] 3>∞-6 2

M P
A B C D A B C D
A 0 -2 4 1 A A C A C
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 -3 C 0 C C B
D ∞ ∞ 2 0 D 0 0 D D
 K=3 5
A B
i=3

j=1 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] ∞>∞+0 2

M P
A B C D A B C D
A 0 -2 4 1 A A C A C
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 -3 C 0 C C B
D ∞ ∞ 2 0 D 0 0 D D
 K=3 5
A B
i=3

j=2 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] -6 > -6 + 0 2

M P
A B C D A B C D
A 0 -2 4 1 A A C A C
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 -3 C 0 C C B
D ∞ ∞ 2 0 D 0 0 D D
 K=3 5
A B
i=3

j=3 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] 0>0+0 2

M P
A B C D A B C D
A 0 -2 4 1 A A C A C
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 -3 C 0 C C B
D ∞ ∞ 2 0 D 0 0 D D
 K=3 5
A B
i=3

j=4 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] -3 > 0 + -3 2

M P
A B C D A B C D
A 0 -2 4 1 A A C A C
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 -3 C 0 C C B
D ∞ ∞ 2 0 D 0 0 D D
 K=3 5
A B
i=4

j=1 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] ∞ > 2 + ∞ 2

M P
A B C D A B C D
A 0 -2 4 1 A A C A C
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 -3 C 0 C C B
D ∞ ∞ 2 0 D 0 0 D D
 K=3 5
A B
i=4

j=2 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] ∞>2+∞ 2

M P
A B C D A B C D
A 0 -2 4 1 A A C A C
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 -3 C 0 C C B
D ∞ ∞ 2 0 D 0 0 D D
 K=3 5
A B
i=4

j=3 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] 2>2+0 2

M P
A B C D A B C D
A 0 -2 4 1 A A C A C
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 -3 C 0 C C B
D ∞ ∞ 2 0 D 0 0 D D
 K=3 5
A B
i=4

j=3 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] 0 > 2 + -3 2

M P
A B C D A B C D
A 0 -2 4 1 A A C A C
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 -3 C 0 C C B
D ∞ ∞ 2 0 D 0 0 D D
 K=3 5
A B
i=4

j=3 4 -6 3

C D
M[ i , j] > M[ i , k]+ M[k, j] 0 > -1 2

M P
A B C D A B C D
A 0 -2 4 1 A A C A C
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 -3 C 0 C C B
D ∞ ∞ 2 -1 D 0 0 D C
 K=3 5
A B
i=4

j=3 4 -6 3

C D
M[D, D] < 0 A negative cycle exists 2

M P
A B C D A B C D
A 0 -2 4 1 A A C A C
B ∞ 0 ∞ 3 B 0 B 0 B
C ∞ -6 0 -3 C 0 C C B
D ∞ ∞ 2 -1 D 0 0 D C
 Exercise 2
• Compute the shortest path between each pair of Vertex,

5
A B

3
4 -6

C D
2