1
Université De Tiaret
Département Informatique
Le Mini Projet
Sujet 02
Algorithme De Ballman Ford
GROUPE 01
Keroum Ahmed Faycal.
Boufarse Mohamed Karim .
Kadi Rayan.
Sous La Supervision De Professeur
Daoud Hayet.
Année Scolaire 2020/2021
2
Indice
1. Introduction ……………………..(3)
2. Historiquement Algorithme Bellmen Ford……..(4)
2.1 Richard Ernest Bellman …………(5)
2.2 Lester Randolph Ford junior ……(5)
3. Algorthme Bellman Ford………………. (6)
4. Structure Algorithme Bellman Ford………..(7)
4.1 Structure Algorithme Bellman Ford Jeux D’essai…….(7)
4.2 Structure Algorithme Bellman Ford Initialisation……(8)
4.3 Structure Algorithme Bellman Ford Relaxation…(8)
4.4 Structure Algorithme Bellman Ford Contrôle…(11)
5.Exploitation des resultat………………………………(12)
5.1.Exploitation des resultat Graphe le plus court chemin……(13)
Pdf Mini Projet Sur Site
https://drive.google.com/folderview?id=1JrQzea3s8YnjjirY7GggEo90FaB3z8-S
3
1.Introduction :
Algorithme de Dijkstra C'est un algorithme efficace
pour gérer le chemin de source unique le plus court,
mais il est limité au cas où le poids d'arête est non
négatif. L'algorithme de Dijkstra échouera et le chemin
le plus court trouvé peut être erroné.
L'algorithme Floyd-Warshall-Roy fonctionne sur tous
les graphiques mais il présente deux inconvénients
• Le temps de calcul est trop long
Cela consomme beaucoup de mémoire
À ce stade, d'autres algorithmes doivent être utilisés
pour résoudre les chemins les plus courts et les moins
chers. Le premier d'entre eux est l'algorithme Bellman-
Ford.
C'est le sujet de notre recherche.
https://arabicprogrammer.com
4
2.Historiquement Algorithme Bellmen Ford :
L'algorithme de Bellman-Ford, aussi appelé algorithme
de Bellman–Ford–Moore est un algorithme qui calcule
des plus courts chemins depuis un sommet source
donné dans un graphe orienté pondéré. Il porte le nom
de ses inventeurs Richard Bellman et Lester Randolph
Ford junior (publications en 1956 et 1958), et de Edward
Forrest Moore qui le redécouvrit en 1959.
Algorithme de Bellman-Ford
Découvreurs ou Richard Bellman (1958), L. R. Ford,
inventeurs Jr. (1956), Edward F. Moore (1957)
Algorithme de recherche de chemin (d),
Problèmes liés algorithme de la théorie des graphes (d),
concept mathématique (d)
Structure des Graphe
données
Contrairement à l'algorithme de Dijkstra, l'algorithme de
Bellman-Ford autorise la présence de certains arcs de
poids négatif et permet de détecter l'existence
5
d'un circuit absorbant, c'est-à-dire de poids total
strictement négatif.
Richard Ernest Bellman
né le 29 août 1920 à Brooklyn et mort
le 19 mars 1984 à Los Angeles) est
un mathématicien américain. Il étudia les mathématiques
appliquées. Célèbre pour diverses contributions dans
plusieurs domaines des mathématiques, il est surtout
l'inventeur de la programmation dynamique,qui résolut à
son époque sommes de fonctions monotones
croissantes sous contraintes de façon inespérée
l'optimisation des sommes de fonctions monotones
croissantes sous contraintes
https://fr.m.wikipedia.org/wiki/Richard_Bellman
Lester Randolph Ford junior (né le 23 septembre
1927 à Houston et mort le 26 février 2017) est
un mathématicien
6
americain spécialiste desproblèmesdes réseaux de
transport.Il est le fils du mathématicien Lester R. Ford
senior[1].
https://fr.m.wikipedia.org/wiki/Lester_Randolph_Ford_junior
3.Algorthme Bellman Ford :
Graphe=(S;A)
Cij appartient R(<=0 ou >=0)
Cxy=∞ s’il n’ y a pas d’arc entre x et y Declaration
Bellamn Ford(G ,C,s)
G=Graph C=Cij s=point initial
d(s) 0;
pour chaque v Ɛ S (sauf(s)) faire intialisation
d(v) ∞;
fin pour ;
Pour i 1 jusque s-1
Faire, pour chaque arc(u,v) Ɛ A
faire :
Si d(v)>d(u)+c(u,v) alors Relaxation
d(v) d(u)+c(u,v) ;
7
fin si ;
fin pour ;
pour chaque arc(u,v) Ɛ A Faire
si d(v)>d(u) + c(u,v) ;
Alors Existence d’un boucle negative
Sinon retour a d(v) Contrôle
Fin si ;
Fin pour ;
4.Structer Algorthme Bellman Ford.
B D
3 3
-2
A 9
F
3
-5 2
4 1
C E
8
d(v),d(u) :le poids
C(u,v): le chemain
Initialisation :
d(s) 0;
pour chaque v Ɛ S (sauf(s)) faire
d(v) ∞;
fin pour ;
A B C D E F Sommet
Init 0 ∞ ∞ ∞ ∞ ∞
Relaxation :
Iteration n01
S=6 Sommets soit s-1 =5 iterations
Pour i 1 jusque s-1
Faire, pour chaque arc(u,v) Ɛ A
faire :
Si d(v)>d(u)+c(u,v) alors
d(v) d(u)+c(u,v) ;
fin si ;
fin pour ;
9
AB (…. ;….+…..)
AB (d(b) ;d(a)+c(a→b))
AB (∞ ;0+3) d(b)= 3 car ∞>0+3
d(c) ;d(a)+c(a→c)
AB (∞ ;0+3) d(b)=3 DB (∞ ; ∞-2) d(b)= ∞
AC (∞ ;0+4) d(c)=4 ED (∞ ; ∞+3) d(d)= ∞
BC (∞ ; ∞+9) d(c)= ∞ CD (∞ ; ∞+-5) d(d)= ∞
BE (∞ ; ∞+2) d(e)=∞ DF (∞ ; ∞+3) d(f)= ∞
BD (∞ ; ∞+2) d(d)= ∞ EF (∞ ; ∞+1) d(f)= ∞
Sommet
A B C D E F
Init 0 ∞ ∞ ∞ ∞ ∞
1 0 3 ;A 4 ;A ∞ ∞ ∞
Iteration n02
AB (∞ ;0+3) d(b)=3 DB (∞ ; ∞-2) d(b)= ∞
AC (∞ ;0+4) d(c)=4 ED (∞ ; ∞+3) d(d)= ∞
BC (∞ ; ∞+9) d(c)= ∞ CD (∞ ; ∞+-5) d(d)= ∞
BE (∞ ; ∞+2) d(e)=∞ DF (∞ ; ∞+3) d(f)= ∞
BD (∞ ; ∞+2) d(d)= ∞ EF (∞ ; ∞+1) d(f)= ∞
10
Sommet
A B C D E F
Init 0 ∞ ∞ ∞ ∞ ∞
1 0 3 ;A 4 ;A ∞ ∞ ∞
2 0 3 ;A 4 ;A -1 ;C 5 ;B ∞
(Pour iteration 3 et 4 et 5 en fait le meme)
Iteration n05
AB (∞ ;0+3) d(b)=3 DB (∞ ; ∞-2) d(b)= ∞
AC (∞ ;0+4) d(c)=4 ED (∞ ; ∞+3) d(d)= ∞
BC (∞ ; ∞+9) d(c)= ∞ CD (∞ ; ∞+-5) d(d)= ∞
BE (∞ ; ∞+2) d(e)=∞ DF (∞ ; ∞+3) d(f)= ∞
BD (∞ ; ∞+2) d(d)= ∞ EF (∞ ; ∞+1) d(f)= ∞
Sommet
A B C D E F
Init 0 ∞ ∞ ∞ ∞ ∞
1 0 3 ;A 4 ;A ∞ ∞ ∞
2 0 3 ;A 4 ;A -1 ;C 5 ;B ∞
3 0 -3 ;D 4;A -1 ;C 5 ;B 2 ;D
4 0 -3 ;D 4;A -1 ;C -1 ;B 2 ;D
5 0 -3 ;D 4;A -1 ;C -1 ;B 0 ;E
11
Contrôle :
pour chaque arc(u,v) Ɛ A Faire
si d(v)>d(u) + c(u,v) ;
Alors Existence d’un boucle negative
Sinon retour a d(v)
Fin si ;
Fin pour ;
-Consiste a controler la non existence d’une boucle negative.
-Permet de verifier que la derniere iteration est bien la
bonne.
Sommet
A B C D E F
Init 0 ∞ ∞ ∞ ∞ ∞
1 0 3 ;A 4 ;A ∞ ∞ ∞
2 0 3 ;A 4 ;A -1 ;C 5 ;B ∞
3 0 -3 ;D 4;A -1 ;C 5 ;B 2 ;D
4 0 -3 ;D 4;A -1 ;C -1 ;B 2 ;D
5 0 -3 ;D 4;A -1 ;C -1 ;B 0 ;E
Controle -3 4 -1 -1 0
-on a fini le contrôle le rusltat pas de boucle negative.
12
5.Exploitation des resultat :
Sommet
A B C D E F
Init 0 ∞ ∞ ∞ ∞ ∞
1 0 3 ;A 4 ;A ∞ ∞ ∞ A
2 0 3 ;A 4 ;A -1 ;C 5 ;B ∞ C
3 0 -3 ;D 4;A -1 ;C 5 ;B 2 ;D D
4 0 -3 ;D 4;A -1 ;C -1 ;B 2 ;D B
5 0 -3 ;D 4;A -1 ;C -1 ;B 0 ;E E
F
B D
3 3
-2
A 9
F
3
-5 2
4 1
C E
Graphe le plus court chemin
13
https://youtu.be/_Lh8pkztw40
En fin
l’algorithme de Bellman-Ford fonctionne sur tout les graphes mais a un
temps de calcul encore relativement long
(∼ n2 × m ≈ n3)
mais consomme
moins de m´emoire.
