University of Algiers 1

Benyouçef Benkhedda

Graph Theor y
Shor test Path Probl em
Course intended for students in L2 Computer Science

Presented by
Dr. BOUFENAR Chaouki
Associate Professor, University of Algiers 1
[Link]@[Link]

2024/2025
 Shortest Path Problem
In graph theory, the Shortest Path Problem consists of finding a path between two vertices in a graph such that the
sum of the weights of its constituent arcs is minimal.

Problem
Let us consider a graph 𝑮 = 𝑉, 𝐸 with a weighting function f that maps to each edge e a weight (length) c with real
value..

𝑗
The problem is to find an elementary path 𝐋 between a pair of vertices 𝒆𝐢 , 𝒆𝐣 such as: c 𝐋 = σ𝑖=1 𝑐 𝒆𝐢−𝟏 , 𝒆𝐢 be as
small as possible.

Example
2 1
a b c

𝟏𝟑
5
He shortest path between a and d : 𝐋 = 𝐚, 𝐛, 𝐜, 𝐝 and c 𝐋 = 8
d
31/12/2024 2
 Shortest Path Problem
Different variants of the problem

Shortest Path with Shortest Path with a Shortest Path for all pairs Shortest Path for one pair of
a unique Source unique Destination of vertices vertices

31/12/2024 3
 Shortest Path Problem
Different variants of the problem

Shortest Path with Shortest Path with a Shortest Path for all pairs Shortest Path for one pair of
a unique Source unique Destination of vertices vertices

 Find a shortest path from a given source vertex S to any vertex v.

 The Dijkstra algorithm and the Bellman-Ford algorithm are best suited to solve this problem.

31/12/2024 4
 Shortest Path Problem
Different variants of the problem

Shortest Path with Shortest Path with a Shortest Path for all pairs Shortest Path for one pair of
a unique Source unique Destination of vertices vertices

 Find a shortest path to a destination vertex d from any vertex e.

 By reversing the direction of each arc of the graph, we can reduce this problem to a unique source problem.

 Dijkstra's algorithm is best suited to solve this variant.

31/12/2024 5
 Shortest Path Problem
Different variants of the problem

Shortest Path with Shortest Path with a Shortest Path for all pairs Shortest Path for one pair of
a unique Source unique Destination of vertices vertices

 Find the shortest path for each pair of vertices.

 The Floyd-Warshall and Johnson algorithms are best suited to this problem.
 The weights of the edges can be negative numbers as long as there are no negative weight circuits.
 This variant can be solved by running a unique source algorithm from each vertex..

31/12/2024 6
 Shortest Path Problem
Different variants of the problem

Shortest Path with Shortest Path with a Shortest Path for all pairs Shortest Path for one pair of
a unique Source unique Destination of vertices vertices

 Find a shortest path from vertex 𝒆𝟏 to vertex 𝒆𝟐 .

 The well-known 𝐀∗ search algorithm is used to solve this problem variant.

 By resolving the unique source variant of the problem, we inherently address this variant as well.

31/12/2024 7
 Shortest Path with a unique Source
Case of negative arc weight
If there exists a circuit of strictly negative length accessible from s, the length of a shortest path is no longer well defined if
its value is negative.
3
Example
s 6 b c 6 d

-6
 The circuit (b,c,b) having the length 3 + (−6) = −3 < 0, there is no shortest path from s to b.

 Every time we traverse the circuit (b, c, b), we can identify paths between s and d with strictly negative lengths that
are arbitrarily large in absolute value.
• Path 1 : (s,b) of length 6
• Path 2 : (s,b,c,b) of length 6+3+(-6)= 3 Length of path from s to d is : → (−∞)
• Path 3 : (s,b,c,b,c,b) of length 6+3+(-6)+3+(-6)= 0
…….
• Path 10 : (s,b,c,b,c,b,…….,b) of length 6+3+(-6)+3+(-6)+3+….= -21

8
 Shortest Path with a unique Source
Dijkstra Algorithm (1959)
Compute the shortest path in graphs that may have cycles and whose weights are positive or zero.
Input: A graph 𝐺 = 𝑉, 𝐸, 𝑐 such as:
𝑿 = 𝑛 ; 𝑼 = 𝑝 ; c : function de cout (c ∶ 𝑈 → 𝑅 + ) ; s : Sommet source
Output: a path of minimum length
Begin
𝜋 𝑖 x : length of the shortest path from s to v at step i
𝜋 𝑠 ←0
𝜋 𝑣 ← ∞ ∀𝑣 ∈ 𝑉 − 𝑠
Edsger Dijkstra
Mark s
(1930-2002)
k ←1
While ∃ 𝑎𝑛 𝑢𝑛𝑚𝑎𝑟𝑘𝑒𝑑 𝑣𝑒𝑟𝑡𝑒𝑥 Do
For each vertex v unmarked with at least one marked predecessor Do
𝜋 𝑘 𝑣 = min 𝜋 𝑘−1 v𝑘−1 + 𝑑 v𝑘−1 , v , 𝜋 𝑘−1 v
End For
𝒆𝒌 ← 𝒆 # 𝑠𝑢𝑐ℎ 𝑎𝑠 𝜋 𝑘 v 𝑖𝑠 𝑡ℎ𝑒 𝑚𝑖𝑛𝑖𝑚𝑢𝑚 𝑎𝑚𝑜𝑛𝑔 𝑡ℎ𝑒 𝑢𝑛𝑚𝑎𝑟𝑘𝑒𝑑 𝑣𝑒𝑟𝑡𝑖𝑐𝑒𝑠
Mark 𝒆𝒌 and the arc that gave the minimum
k ← 𝑘 +1
End While
End
31/12/2024 9
 Shortest Path with a unique Source
Dijkstra Algorithm (1959)
𝟑
Example A D
2 1 2 0

S 0 C 1 F
1 1
3 3
B 𝟑 E

Step Marked vertices S A B C D E F

0 ∞ ∞ ∞ ∞ ∞ ∞
K=1
K=2
K=3
K=4
K=5
31/12/2024 K=6 10
 Shortest Path with a unique Source
Dijkstra Algorithm (1959)
𝟑
A D
2 1 2 0
∗
S 0 C 1 F
1 1
3 3
B 𝟑 E

Step Market vertices S A B C D E F

𝑆 0 ∞ ∞ ∞ ∞ ∞ ∞
K=1
K=2
K=3
K=4
K=5
31/12/2024 K=6 11
 Shortest Path with a unique Source
Dijkstra Algorithm (1959)
𝟑
Exemple A D
2 1 2 0
∗
S 0 C 1 F
1 1
3 3
B 𝟑 E

𝜋 1 A = min 𝜋 0 𝑆 + 𝑑 𝑆, 𝐴 , 𝜋 0 𝐴 = min 0 + 2, ∞ = 2 𝜋 1 B = min 𝜋 0 𝑆 + 𝑑 𝑆, 𝐵 , 𝜋 0 𝐵 = min 0 + 3, ∞ = 3

Step Market vertices S A B C D E F

𝑆 0 ∞ ∞ ∞ ∞ ∞ ∞
K=1 2 3 ∞ ∞ ∞ ∞
K=2
K=3
K=4
K=5
31/12/2024 K=6 12
 Shortest Path with a unique Source
Dijkstra Algorithm (1959)
∗
𝟑
Exemple A D
2 1 2 0
∗
S 0 C 1 F
1 1
3 3
B 𝟑 E

𝜋 1 A = min 𝜋 0 𝑆 + 𝑑 𝑆, 𝐴 , 𝜋 0 𝐴 = min 0 + 2, ∞ = 2 𝜋 1 B = min 𝜋 0 𝑆 + 𝑑 𝑆, 𝐵 , 𝜋 0 𝐵 = min 0 + 3, ∞ = 3

Step Market vertices S A B C D E F

K=0 𝑆 0 ∞ ∞ ∞ ∞ ∞ ∞
K=1 𝑆, 𝐴 2 3 ∞ ∞ ∞ ∞
K=2
K=3
K=4
K=5
31/12/2024 K=6 13
 Shortest Path with a unique Source
Dijkstra Algorithm (1959)
∗
𝟑
Exemple A D
2 1 2 0
∗
S 0 C 1 F
1 1
3 3
B 𝟑 E
𝜋 2 B = min 𝜋1 𝐴 + 𝑑 𝐴, 𝐵 , 𝜋 1 𝐵 = min 2 + 0,3 = 2 𝜋 2 D = min 𝜋 1 𝐴 + 𝑑 𝐴, 𝐷 , 𝜋 1 𝐷 = min 2 + 3, ∞ = 5

Step Market vertices S A B C D E F

𝑆 0 ∞ ∞ ∞ ∞ ∞ ∞
K=1 𝑆, 𝐴 2 3 ∞ ∞ ∞ ∞
K=2 2 ∞ 5 ∞ ∞
K=3
K=4
K=5
31/12/2024 K=6 14
 Shortest Path with a unique Source
Dijkstra Algorithm (1959)
∗
𝟑
Exemple A D
2 1 2 0
∗
S 0 C 1 F
1 1
3 3
∗
B 𝟑 E
𝜋 2 B = min 𝜋1 𝐴 + 𝑑 𝐴, 𝐵 , 𝜋 1 𝐵 = min 2 + 0,3 = 2 𝜋 2 D = min 𝜋 1 𝐴 + 𝑑 𝐴, 𝐷 , 𝜋 1 𝐷 = min 2 + 3, ∞ = 5

Step Market vertices S A B C D E F

K=0 𝑆 0 ∞ ∞ ∞ ∞ ∞ ∞
K=1 𝑆, 𝐴 2 3 ∞ ∞ ∞ ∞
K=2 𝑆, 𝐴, 𝐵 2 ∞ 5 ∞ ∞
K=3
K=4
K=5
31/12/2024 K=6 15
 Shortest Path with a unique Source
Dijkstra Algorithm (1959)
∗
𝟑
Exemple A D
2 1 2 0
∗
S 0 C 1 F
1 1
3 3
∗
B E 𝜋 3 C = min 𝜋 2 𝐵 + 𝑑 𝐵, 𝐶 , 𝜋 2 𝐶 =3
𝟑

𝜋 3 E = min 𝜋 2 𝐵 + 𝑑 𝐵, 𝐸 , 𝜋 2 𝐸 = min 2 + 3, ∞ = 5 𝜋 3 D = min 𝜋 2 𝐴 + 𝑑 𝐴, 𝐷 , 𝜋 2 𝐷 = min 2 + 3,5 = 5

Step Market vertices S A B C D E F

𝑆 0 ∞ ∞ ∞ ∞ ∞ ∞
K=1 𝑆, 𝐴 2 3 ∞ ∞ ∞ ∞
K=2 𝑆, 𝐴, 𝐵 2 ∞ 5 ∞ ∞
K=3 3 5 5 ∞
K=4
K=5
31/12/2024 K=6 16
 Shortest Path with a unique Source
Dijkstra Algorithm (1959)
∗
𝟑
A D
2 1 2 0
∗ ∗
S 0 C 1 F
1 1
3 3
∗
B E 𝜋 3 C = min 𝜋 2 𝐵 + 𝑑 𝐵, 𝐶 , 𝜋 2 𝐶 =3
𝟑

𝜋 3 E = min 𝜋 2 𝐵 + 𝑑 𝐵, 𝐸 , 𝜋 2 𝐸 = min 2 + 3, ∞ = 5 𝜋 3 D = min 𝜋 2 𝐴 + 𝑑 𝐴, 𝐷 , 𝜋 2 𝐷 = min 2 + 3,5 = 5

Step Market vertices S A B C D E F

𝑆 0 ∞ ∞ ∞ ∞ ∞ ∞
K=1 𝑆, 𝐴 2 3 ∞ ∞ ∞ ∞
K=2 𝑆, 𝐴, 𝐵 2 ∞ 5 ∞ ∞
K=3 𝑆, 𝐴, 𝐵, 𝐶 𝟑 5 5 ∞
K=4
K=5
31/12/2024 K=6 17
 Shortest Path with a unique Source
Dijkstra Algorithm (1959)
∗
𝟑
A D
2 1 2 0
∗ ∗
S 0 C 1 F
1 1
3 3
∗
B 𝟑 E
𝜋 3 E = min 𝜋 3 𝐶 + 𝑑 𝐶, 𝐸 , 𝜋 3 𝐸 = min 3 + 1,5 = 4 𝜋 4 D = min 𝜋 3 𝐶 + 𝑑 𝐶, 𝐷 , 𝜋 3 𝐷 = min 3 + 2,5 = 5

Step Market vertices S A B C D E F

K=0 𝑆 0 ∞ ∞ ∞ ∞ ∞ ∞
K=1 𝑆, 𝐴 2 3 ∞ ∞ ∞ ∞
K=2 𝑆, 𝐴, 𝐵 2 ∞ 5 ∞ ∞
K=3 𝑆, 𝐴, 𝐵, 𝐶 𝟑 5 5 ∞
K=4 5 4 ∞
K=5
31/12/2024 K=6 18
 Shortest Path with a unique Source
Dijkstra Algorithm (1959)
∗
𝟑
A D
2 1 2 0
∗ ∗
S 0 C 1 F
1 1
3 ∗ 3
∗
B 𝟑 E
𝜋 4 E = min 𝜋 3 𝐶 + 𝑑 𝐶, 𝐸 , 𝜋 3 𝐸 = min 3 + 1,5 = 4

Step Market vertices S A B C D E F

𝑆 0 ∞ ∞ ∞ ∞ ∞ ∞ 𝜋 4 𝐃 = 𝑚𝑖𝑛 𝜋 3 𝐶 + 𝑑 𝐶, 𝐷 , 𝜋 3 𝐷
K=1 𝑆, 𝐴 2 3 ∞ ∞ ∞ ∞ = 𝑚𝑖𝑛 3 + 2; 5 = 𝟓

K=2 𝑆, 𝐴, 𝐵 2 ∞ 5 ∞ ∞
K=3 𝑆, 𝐴, 𝐵, 𝐶 𝟑 5 5 ∞ 𝜋 4 𝐄 = 𝑚𝑖𝑛 𝜋 3 𝐶 + 𝑑 𝐶, 𝐸 , 𝜋 3 𝐸
= 𝑚𝑖𝑛 3 + 1; 5 = 𝟒
K=4 𝑆, 𝐴, 𝐵, 𝐶, 𝐸 5 4 ∞
K=5
K=6 31/12/2024 19
 Shortest Path with a unique Source
Dijkstra Algorithm (1959)
∗
𝟑
A D
2 1 2 0
∗ ∗
S 0 C 1 F
1 1
3 ∗ 3
∗
B 𝟑 E

Step Market vertices S A B C D E F

K=0 𝑆 0 ∞ ∞ ∞ ∞ ∞ ∞
𝜋 5 𝐃 = 𝑚𝑖𝑛 𝜋 4 𝐸 + 𝑑 𝐸, 𝐷 , 𝜋 4 𝐷
K=1 𝑆, 𝐴 2 3 ∞ ∞ ∞ ∞ = 𝑚𝑖𝑛 4 + 1; 5 = 𝟓
K=2 𝑆, 𝐴, 𝐵 2 ∞ 5 ∞ ∞
K=3 𝑆, 𝐴, 𝐵, 𝐶 𝟑 5 5 ∞ 𝜋 5 𝐅 = 𝑚𝑖𝑛 𝜋 4 𝐸 + 𝑑 𝐸, 𝐹 , 𝜋 4 𝐹
K=4 𝑆, 𝐴, 𝐵, 𝐶, 𝐸 5 4 ∞ = 𝑚𝑖𝑛 4 + 3; ∞ = 𝟕

K=5 5 7
K=6
31/12/2024 20
 Shortest Path with a unique Source
Dijkstra Algorithm (1959)
∗ ∗
𝟑
A D
2 1 2 0
∗ ∗
S 0 C 1 F
1 1
3 ∗ 3
∗
B 𝟑 E

Step Market vertices S A B C D E F

𝑆 0 ∞ ∞ ∞ ∞ ∞ ∞
K=1 𝑆, 𝐴 2 3 ∞ ∞ ∞ ∞ 𝜋 6 F = 𝑚𝑖𝑛 𝜋 5 𝐷 + 𝑑 𝐷, 𝐹 , 𝜋 5 𝐹
K=2 𝑆, 𝐴, 𝐵 2 ∞ 5 ∞ ∞ = 𝑚𝑖𝑛 5 + 0; 7 = 𝟓

K=3 𝑆, 𝐴, 𝐵, 𝐶 𝟑 5 5 ∞
K=4 𝑆, 𝐴, 𝐵, 𝐶, 𝐸 5 4 ∞
K=5 𝑆, 𝐴, 𝐵, 𝐶, 𝐸, 𝐷 5 7
K=6 31/12/2024 5 21
 Shortest Path with a unique Source
Dijkstra Algorithm (1959)
∗ ∗
𝟑
A D
2 1 2 0
∗ ∗ ∗
S 0 C 1 F
1 1
3 ∗ 3
∗
B 𝟑 E

Step Market vertices S A B C D E F

𝑆 0 ∞ ∞ ∞ ∞ ∞ ∞
K=1 𝑆, 𝐴 2 3 ∞ ∞ ∞ ∞
K=2 𝑆, 𝐴, 𝐵 2 ∞ 5 ∞ ∞
K=3 𝑆, 𝐴, 𝐵, 𝐶 𝟑 5 5 ∞
K=4 𝑆, 𝐴, 𝐵, 𝐶, 𝐸 5 4 ∞
K=5 𝑆, 𝐴, 𝐵, 𝐶, 𝐸, 𝐷 5 7
K=6 31/12/2024
𝑆, 𝐴, 𝐵, 𝐶, 𝐸, 𝐷, 𝐹 5 22
 Shortest Path with a unique Source
Dijkstra Algorithm (1959)

Source Destination Path Distance

𝐒 A S →A 2
𝐒 B S→A→B 2
𝐒 C S →A→B→C 3
𝐒 D S→A→B→C→E→D 5
𝐒 E S → A → B → C→ E 4
𝐒 F S →A→B→ C→E→D 5

31/12/2024 23
 Shortest Path with a unique Source
Bellman-Ford Algorithm (Ageneral algorithm of Ford)
Unlike Dijkstra's algorithm, which is limited to graphs with non-negative edge weights, the Bellman-Ford algorithm
accommodates graphs with negative edge weights and can detect the presence of an absorbing circuit (one with a negative
total weight) reachable from the source vertex.

Principle of the algorithm

The Bellman-Ford algorithm (also known as the general Ford algorithm) operates on the principle of iteratively improving an
initial feasible arborescence (V,A) with root 𝑠 until it yields an optimal arborescence representing the shortest paths originating
from 𝑠, if exists.

NB. Dijkstra's algorithm can be used to generate a feasible arborescence from which to launch the search for the longest path.

31/12/2024 24
 Shortest Path with a unique Source
Bellman-Ford Algorithm (Ageneral algorithm of Ford)
Input : A graph 𝐺 = 𝑉, 𝐸, 𝑑 such as:
𝑿 = 𝑛 ; 𝑼 = 𝑝 ; c : Cost function (d: 𝑈 → 𝑅 ) ; s : Source vertex ; X, A : an initial arborescence of root 𝐬
Output: An arborescence of the shortest paths from a root 𝐬
Beging
𝜋 x : length of the shortest path from s to v. 𝜋 𝑠 ← 0
Step 1 : Search an edge e = e1 , e2 ∈ 𝐸 − 𝐴 such as : 𝛿 𝑒 = 𝜋 e2 − 𝜋 e1 − 𝑑 e1 , e2 > 0
If this edge un tel arc n'existe pas; Stop, (X,A) est
optimale.
Sinon an
Step 2 : Search Goto Step
edge e=2 e1 , e2 ∈ 𝐸 − 𝐴 such as : 𝛿 𝑒 = 𝜋 e2 − 𝜋 e1 − 𝑑 e1 , e2 > 0
If V, A ∪ e includes a circuit Then
If this circuit is absorbing Then
Stop (The problem has no solution).
Else Goto Step 3
Step 3 : Search an edge t ∈ 𝐴 such as: T t = 𝑒2

Let 𝑉 ′ = e2 ∪ {descendants of e2 in the arborescence V, A }

𝜋 𝑦 = 𝜋 𝑦 − 𝛿 𝑒 ∀ 𝑦 ∈ 𝑉′
Goto Step 1
End 31/12/2024 25
 Shortest Path with a unique Source
Bellman-Ford Algorithm (Ageneral algorithm of Ford)
Exemple A 𝟐 D
3 2 2 2

S -3 C 3 F
0 2
2 6
B E
1

Ce graphe ne possède pas de circuit absorbant et le sommet S est une racine; alors ce problème admet une arborescence
des plus courts chemins.
Initialisation : X, A : une arborescence initiale d′ une racine 𝐬
3 5
A 𝟐 D
3 2 2 2
0 5 7
S -3 C 3 F
0 2
2 2 3 6
B E
31/12/2024 1 26
 Shortest Path with a unique Source
Bellman-Ford Algorithm (Ageneral algorithm of Ford)
Iteration 01 : In G the arcs not belonging to A are: A, B ; A, C ; C, B ; C, D ; E, D ; E, F
Step 1 3 5
𝛿 A, B = 𝜋 𝐵 − 𝜋 𝐴 − 𝑑 A, B =2−3+3 =2 A 𝟐 D
𝛿 A, 𝐶 = 𝜋 𝐶 − 𝜋 𝐴 − 𝑑 A, 𝐶 =5−3−2 = 0 3 2 2 2
𝛿 C, B = 𝜋 𝐵 − 𝜋 𝐶 − 𝑑 C, B = 2 − 5 − 0 = −3 0 5 7
S -3 C 3 F
𝛿 C, 𝐷 = 𝜋 𝐷 − 𝜋 𝐶 − 𝑑 C, 𝐷 = 5 − 5 − 2 = −2
0 2
𝛿 E, 𝐷 = 𝜋 𝐷 − 𝜋 𝐸 − 𝑑 E, 𝐷 = 5 − 3 − 3 = −1
2 2 3 6
𝛿 E, 𝐹 = 𝜋 𝐹 − 𝜋 𝐸 − 𝑑 E, 𝐹 = 7 − 3 − 6 = −2 B E
1
Step 2
The arc u = A, B A and 𝛿 u > 0 and A∪ 𝑢 does not contains a circuit, then the arc u =(A,B) enters the l'arborescence.
Step 3
3 5
The arc v = S, B ∈ A, T (v) = 3 then the arc v exits the arborescence. A 𝟐 D
X ′= B ∪ {descendants of the vertex B in the l'arborescence 3 2 2 2
0 3 7
X, A }={B,C,E}
𝜋 𝐵 = 𝜋 𝐵 − 𝛿 A, 𝐵 = 2 − 2 = 0 S -3 C 3 F
𝜋 𝐶 = 𝜋 𝐶 − 𝛿 A, 𝐵 = 5 − 2 = 3 0 2
𝜋 𝐸 = 𝜋 𝐸 − 𝛿 A, 𝐵 = 3 − 2 = 1 2 0 1 6
31/12/2024 B E 27
1
 Shortest Path with a unique Source
Bellman-Ford Algorithm (Ageneral algorithm of Ford)
Iteration 02 : In G the arcs not belonging to A are: S, B ; A, C ; C, B ; C, D ; E, D ; E, F
Step 1 3 5
A 𝟐 D
𝛿 S, B =𝜋 𝐵 −𝜋 𝑆 −𝑑 S, B = 0 − 0 − 2 = −2
𝛿 A, 𝐶 =𝜋 𝐶 −𝜋 𝐴 −𝑑 A, 𝐶 = 3 − 3 − 2 = −2 3 2 2 2
0 3 7
𝛿 C, 𝐵 =𝜋 𝐵 −𝜋 𝐶 −𝑑 C, 𝐵 = 0 − 3 − 0 = −3 S -3 C F
3
𝛿 C, 𝐷 =𝜋 𝐷 −𝜋 𝐶 −𝑑 C, 𝐷 =5−3−2 =0 0 2
𝛿 E, 𝐷 =𝜋 𝐸 −𝜋 𝐷 −𝑑 E, 𝐷 =5−1−3=1 2 0 1 6
𝛿 E, 𝐹 = 𝜋 𝐹 − 𝜋 𝐸 − 𝑑 E, 𝐹 = 7 − 1 − 6 = 0 B E
1

The arc u = E, 𝐷 A and 𝛿 u > 0 and A ∪ 𝑢 does not contain a circuit, so the arc (E,𝐷) enters the arborescence.
Step 2
The arc v = A, 𝐷 ∈ A, T (v) = D, then the arc v exits the l'arborescence. 3 4
A 𝟐 D
Step 3
3 2 2 2
0 3 6
X ′= D ∪ {descendants of the vertex D in the arborescence C
S -3 3 F
X, A }={D,F}
𝜋 𝐷 = 𝜋 𝐷 − 𝛿 E, 𝐷 = 5 − 1 =4 0 2
𝜋 𝐹 = 𝜋 𝐹 − 𝛿 E, 𝐷 = 7 − 1 =6 2 0 1 6
B E
31/12/2024 1 28
 Shortest Path with a unique Source
Bellman-Ford Algorithm (Ageneral algorithm of Ford)
Iteration 03 : In G the arcs not belonging to A are: S, B ; A, C ; A, 𝐷 ; C, B ; C, D ; E, F
Step 1
3 4
𝛿 S, B = 𝜋 𝐵 − 𝜋 𝑆 − 𝑑 S, B = 0 − 0 − 2 = −2 𝟐
A D
𝛿 A, 𝐶 = 𝜋 𝐶 − 𝜋 𝐴 − 𝑑 A, 𝐶 = 3 − 3 − 2 = −2 3 2 2 2
0 3 6
𝛿 A, 𝐷 = 𝜋 𝐷 − 𝜋 𝐴 − 𝑑 A, 𝐷 = 4 − 3 − 2 = −1
S -3 C 3 F
𝛿 C, B = 𝜋 𝐵 − 𝜋 𝐶 − 𝑑 C, B = 0 − 3 − 0 = −3 0 2
𝛿 C, 𝐷 = 𝜋 𝐷 − 𝜋 𝐶 − 𝑑 C, 𝐷 = 4 − 3 − 2 = −1 2 0 1 6
B E
𝛿 E, 𝐹 = 𝜋 𝐹 − 𝜋 𝐸 − 𝑑 E, 𝐹 = 6 − 1 − 6 = −1 1

There is no arc u that does not belong to A and 𝛿 u > 0. 3 4

A D
We stop and the the arborescence is optimal. 3 2
0 3 6
S -3 C 3 F
NB. Finding a longest path on the network R=(X,U,d) is 2
0 1
equivalent to finding a shortest path on R=(X,U,-d). B E
1
31/12/2024 29