1

Remerciement
Avant de commencer la présentation de notre rapport

Nous tenons à exprimer notre profonde gratitude envers notre enseignant,

M. J. Abouir, pour nous avoir donné l'opportunité d'étudier et de mettre en
pratique les concepts des algorithmes du plus court chemin, notamment
l'algorithme de Dijkstra et l'algorithme de Bellman-Ford. Son soutien et ses
explications détaillées ont grandement contribué à notre compréhension de
ces sujets complexes. Son dévouement à notre apprentissage est
sincèrement apprécié et a enrichi notre expérience académique en tant que
groupe.

Nous lui sommes reconnaissants pour son encouragement constant et son

engagement envers notre succès académique.

2
 Table des matières
Introduction ....................................................................................................................................................... 5
Chapitre 1 : ......................................................................................................................................................... 6
Introduction aux Graphes.................................................................................................................................. 6
1 Définitions de base : ...................................................................................................................................... 6
2 Types de graphes : ......................................................................................................................................... 7
3 Les Graphes dans python :............................................................................................................................. 8
Chapitre 2 ......................................................................................................................................................... 11
Algorithme de Dijkstra :................................................................................................................................... 11
1 Fonctionnement de l’algorithme : .............................................................................................................. 11
2 Pseudo-Code : .............................................................................................................................................. 13
3 Fonction python de Dijkstra : ...................................................................................................................... 14
4 Test de Dijkstra : .......................................................................................................................................... 15
Chapitre 3 : ....................................................................................................................................................... 16
Algorithme de Bellman-Ford ........................................................................................................................... 16
1 Différence entre Bellman-Ford et Dijkstra: ................................................................................................. 16
2 Fonctionnement de l'Algorithme de Bellman-Ford : ................................................................................... 17
3 Pseudo-Code : .............................................................................................................................................. 18
4 Fonction python de Bellman-Ford : ............................................................................................................. 18
5 Test de Bellman-Ford :................................................................................................................................. 19
Chapitre 4 : ....................................................................................................................................................... 21
Problème Réel de Plus Court Chemin : Système de Navigation GPS ............................................................. 21
1 Description du Problème : ........................................................................................................................... 21
2 Exemple de Graphe Pondéré pour le Réseau Routier Marocain : ............................................................... 21
3 Résolution du problème de plus court chemin : ......................................................................................... 23
Conclusion ........................................................................................................................................................ 24

3
 Liste Des Figures
Figure 1: Graphe orienté pondéré ................................................................................................... 7

Figure 2:Définir un graphe dans python ........................................................................................ 10

Figure 3:Pseudo-code Dijkstra ....................................................................................................... 13

Figure 4: Fonction python de Dijkstra............................................................................................ 14

Figure 5: Test python de Dijkstra ................................................................................................... 15

Figure 6:Pseudo-code Bellman-Ford.............................................................................................. 18

Figure 7: Fonction python de Bellman-Ford .................................................................................. 19

Figure 8: Test python de Bellman-Ford ......................................................................................... 20

Figure 9: Graphe de réseau routier marocain ............................................................................... 22

Figure 10:La résolution de problème............................................................................................. 23

4
 Introduction
La résolution du problème du plus court chemin est essentielle dans de
nombreux domaines, de la logistique à l'ingénierie des réseaux. Elle
consiste à trouver le chemin optimal entre deux points dans un réseau
ou un graphe, en tenant compte des coûts associés à chaque arête ou lien.

La recherche opérationnelle, apparue dans les années 1940, vise à

maximiser l'efficacité de l'utilisation des ressources dans divers
domaines, de l'industrie à la planification militaire. Son développement
s'est accéléré avec l'avènement de l'ordinateur, permettant une résolution
plus rapide et efficace des problèmes complexes.

Dans cette étude, nous examinerons deux algorithmes clés pour résoudre
le problème du plus court chemin : l'algorithme de Dijkstra et
l'algorithme de Bellman-Ford. Nous explorerons leur fonctionnement,
leurs avantages et leurs limitations, ainsi que leur mise en œuvre
pratique en Python.

5
 Chapitre 1
Introduction aux Graphes

Les graphes, en informatique et en mathématiques, sont des structures de données

qui représentent des relations entre des objets. Ils sont largement utilisés pour
modéliser des problèmes dans divers domaines, de la logistique à la biologie en
passant par les réseaux sociaux.

1 Définitions de base :
Un graphe est composé de nœuds (ou sommets) et d'arêtes (ou liens) qui relient
ces nœuds. Ces liens peuvent représenter des connexions ou des relations entre les
nœuds. Le graphe est souvent noté G = (S, A), où S représente l'ensemble des
sommets (ou nœuds) du graphe et A représente l'ensemble des arêtes (ou liens) qui
les relient.

Les graphes peuvent être dirigés, où les arêtes ont une direction, ou non dirigés,
où les arêtes ne sont pas directionnelles.

Dans un graphe orienté, on appelle circuit une suite d'arcs consécutifs (chemin)
dont les deux sommets extrémités sont identiques. La notion correspondante dans
les graphes non orientés est celle de cycle. On parle parfois de cycle orienté. Un
circuit constitué d'un seul arc est une boucle.

Un circuit absorbant dans un graphe est un circuit dans lequel la somme totale des
poids des arêtes est négative. En d'autres termes, c'est un chemin qui forme une

6
 boucle fermée et dont la somme des poids des arêtes le long de ce chemin est
négative. Un tel circuit est également appelé circuit de poids négatif. Les circuits
absorbants peuvent poser des problèmes dans certaines applications, notamment
dans le cadre de l'algorithme de recherche du plus court chemin, car ils peuvent
induire en erreur les calculs de chemins optimaux en présence de poids négatifs.

2 Types de graphes :
Les graphes peuvent être simples, où chaque paire de nœuds est reliée par au plus
une arête, ou multigraphes, où des paires de nœuds peuvent être reliées par
plusieurs arêtes.

Ils peuvent également être pondérés, où chaque arête a un poids associé, ou non
pondérés, où les arêtes n'ont pas de poids.

Les graphes peuvent être orientés, où les arêtes ont une direction définie, ou non
orientés, où les arêtes ne sont pas directionnelles.

On distingue également les graphes avec des circuits absorbants, qui contiennent
au moins un circuit avec un poids total négatif.

Figure 1: Graphe orienté pondéré

7
3 Les Graphes dans python :
Les graphes sont des structures de données fondamentales en informatique,
utilisées pour représenter des relations entre des objets. Python offre plusieurs
bibliothèques puissantes pour travailler avec des graphes, notamment NetworkX,
igraph et graph-tool. Dans ce chapitre, nous explorerons l'utilisation de la
bibliothèque NetworkX pour la manipulation et l'analyse de graphes. Nous
présenterons les fonctionnalités de base de NetworkX, ainsi que des exemples
d'utilisation pour créer, visualiser et analyser des graphes.

 Fonctionnalités de NetworkX :

NetworkX est une bibliothèque Python utilisée pour la création, la manipulation et

l'analyse de structures de réseau complexes. Parmi ses fonctionnalités principales,
on retrouve la possibilité de représenter des graphes non orientés et orientés, des
graphes pondérés et non pondérés, ainsi que des multigraphes. De plus, NetworkX
propose des outils pour générer des graphes aléatoires selon différents modèles et
des algorithmes pour résoudre des problèmes courants liés aux graphes, tels que le
parcours de graphes, la recherche de chemins les plus courts, et bien d'autres.

 Création et Manipulation de Graphes :

Grâce à NetworkX, il est possible de créer des graphes de manière intuitive en

ajoutant des nœuds et des arêtes, ainsi que de manipuler ces structures en ajoutant,
supprimant ou modifiant des éléments. De plus, NetworkX offre des fonctions
permettant d'importer et d'exporter des graphes à partir de divers formats de
fichiers, facilitant ainsi l'échange de données avec d'autres outils ou systèmes.

8
Pour représenter un graphe avec NetworkX, vous pouvez utiliser les fonctions
suivantes :

 [Link](): Pour créer un graphe non orienté.

 [Link](): Pour créer un graphe orienté.

Vous pouvez ajouter des nœuds et des arêtes au graphe en utilisant les méthodes
suivantes :

 G.add_node(): Ajoute un nœud au graphe.

 G.add_edge(): Ajoute une arête entre deux nœuds.

Pour manipuler les graphes, vous disposez des fonctions suivantes :

 G.remove_node(): Supprime un nœud du graphe.

 G.remove_edge(): Supprime une arête du graphe.

 Visualisation de Graphes :

NetworkX inclut des outils de visualisation pour représenter graphiquement les

graphes créés. Ces fonctionnalités de visualisation permettent d'explorer et de
comprendre la structure des graphes de manière visuelle, facilitant ainsi l'analyse
des données et la communication des résultats.

Pour visualiser un graphe avec NetworkX, vous pouvez utiliser la fonction

suivante :

 [Link](): Dessine le graphe.

 Exemple d’utilisation :

9
Figure 2: Définir un graphe dans python

10
 Chapitre 2
Algorithme de Dijkstra

L'algorithme de Dijkstra, proposé par l'informaticien néerlandais Edsger W.

Dijkstra en 1956, est un algorithme classique de recherche de plus court chemin
dans un graphe pondéré, non orienté ou orienté, avec des poids non négatifs sur les
arêtes.

L'algorithme de Dijkstra est largement utilisé dans les réseaux de

télécommunication, les systèmes de cartographie, et d'autres applications
nécessitant la recherche de chemins optimaux dans un graphe. Son efficacité réside
dans sa capacité à trouver rapidement le plus court chemin entre deux nœuds dans
un graphe pondéré. Cet algorithme calcule le chemin le plus court entre un nœud
source et tous les autres nœuds du graphe.

Dans ce chapitre, nous allons présenter l'algorithme de Dijkstra, détailler son

fonctionnement étape par étape, et fournir des exemples d'implémentation en
Python.

1 Fonctionnement de l’algorithme :
L'algorithme de Dijkstra fonctionne selon une approche itérative pour trouver le
chemin le plus court entre un nœud source et tous les autres nœuds dans un graphe
pondéré. Voici un aperçu détaillé de son fonctionnement :

1) Initialisation :

11
-L'algorithme commence par initialiser la distance de chaque nœud depuis le nœud
source à l'infini, sauf pour le nœud source lui-même dont la distance est mise à
zéro.

-Il initialise également un ensemble de nœuds visités vide.

2) Sélection du Nœud Courant :

-À chaque itération, l'algorithme sélectionne le nœud non visité avec la plus petite
distance depuis le nœud source.

3) Mise à Jour des Distances :

-Pour chaque nœud voisin du nœud courant, l'algorithme calcule la distance

minimale jusqu'à ce voisin en passant par le nœud courant.

-Si cette distance calculée est plus petite que la distance actuellement enregistrée
pour le voisin, la distance est mise à jour.

4) Marquage du Nœud Courant comme Visité :

-Une fois que toutes les distances des nœuds voisins ont été mises à jour, le nœud
courant est marqué comme visité et est retiré de l'ensemble des nœuds non visités.

5) Répétition :

-Les étapes 2 à 4 sont répétées jusqu'à ce que tous les nœuds aient été visités ou
jusqu'à ce que la destination souhaitée soit atteinte.

12
 6) Retour des Résultats :
-Une fois que l'algorithme a terminé l'exploration du graphe, il retourne les
distances les plus courtes depuis le nœud source vers tous les autres nœuds.

2 Pseudo-Code :

Figure 3 : Pseudo-code Dijkstra

13
3 Fonction python de Dijkstra :

Figure 4 : Fonction python de Dijkstra

14
4 Test de Dijkstra :

Figure 5 : Test python de Dijkstra

15
 Chapitre 3
Algorithme de Bellman-Ford

L'algorithme de Bellman-Ford, nommé d'après les mathématiciens Richard

Bellman et Lester Ford, est un algorithme classique utilisé dans le domaine de la
théorie des graphes pour résoudre le problème du plus court chemin.
Contrairement à l'algorithme de Dijkstra, l'algorithme de Bellman-Ford peut gérer
les graphes pondérés comportant des arêtes de poids négatif, ce qui le rend plus
polyvalent dans divers scénarios.

1 Différence entre Bellman-Ford et Dijkstra:

L’algorithme de Bellman Ford et l’algorithme de Dijkstra sont tous deux des
algorithmes de chemin le plus court à source unique, c’est-àdire qu’ils déterminent
tous les deux la distance la plus courte entre chaque sommet d’un graphe et un
sommet source unique. Cependant, l'algorithme de Bellman-Ford autorise la
présence de certains arcs de poids négatif et permet de détecter l'existence d'un
circuit absorbant. Alors que l’algorithme de Dijkstra peut fonctionner ou non
lorsqu’il y a un bord de poids négatif. Mais ne fonctionnera certainement pas en
cas de cycle de poids négatif. En termes de complexité, l’algorithme de Bellman
prend plus de temps que celui de Dijkstra. Sa complexité en temps est O(VE), mais
pour celui de Dijkstra c’est O (E log V).

16
2 Fonctionnement de l'Algorithme de Bellman-Ford :
L'algorithme de Bellman-Ford fonctionne selon une approche itérative pour
trouver le chemin le plus court entre un nœud source et tous les autres nœuds dans
un graphe pondéré, même en présence d'arêtes de poids négatif. Voici comment
cet algorithme fonctionne en détail :

1) Initialisation :

-L'algorithme commence par initialiser la distance du nœud initial (I) à zéro et la

distance de tous les autres nœuds à l'infini, sauf le nœud initial lui-même.

2) Boucle Principale :

-L'algorithme effectue une boucle principale de |S|-1 itérations, où |S| est le nombre
de sommets dans le graphe.

-Pour chaque itération de la boucle principale, l'algorithme explore chaque arc (u,
v) dans le graphe et met à jour les distances des nœuds en vérifiant si la distance
actuelle de v est plus grande que la somme de la distance de u et le poids de l'arc
(u, v). Si c'est le cas, la distance de v est mise à jour avec cette nouvelle valeur.

3) Détection de Circuit Absorbant :

-Après avoir effectué |S|-1 itérations, l'algorithme effectue une autre boucle pour
vérifier s'il existe un circuit absorbant dans le graphe. Pour chaque arc (u, v), il
vérifie à nouveau si la distance de v peut être améliorée en passant par u. Si c'est
le cas, cela signifie qu'il y a un circuit absorbant dans le graphe.

4) Résultats :

-Si aucune amélioration n'est possible après |S|-1 itérations, l'algorithme termine
avec succès et retourne les distances les plus courtes de chaque nœud source à tous
les autres nœuds.

17
-Si un circuit absorbant est détecté, cela indique qu'il existe une boucle de poids
négatif dans le graphe, ce qui signifie qu'il n'y a pas de solution aux chemins les
plus courts.

3 Pseudo-Code :

Figure 6 : Pseudo-code Bellman-Ford

4 Fonction python de Bellman-Ford :

18
 Figure 7 : Fonction python de Bellman-Ford

5 Test de Bellman-Ford :
-On va tester avec l’exemple faite dans le cours.

19
Figure 8 : Test python de Bellman-Ford

20
 Chapitre 4
Problème réel de plus court chemin
Système de navigation GPS

1 Description du problème :

Un service de navigation GPS doit être développé pour les voyageurs au Maroc,
permettant de trouver le chemin le plus court entre deux villes. Le réseau routier
marocain est représenté sous forme d'un graphe pondéré, où chaque nœud
représente une ville et chaque arête représente une route entre deux villes, avec un
poids représentant la distance entre ces villes en kilomètres.

Le service doit permettre à un utilisateur de spécifier une ville de départ et une

ville de destination, puis de calculer le chemin le plus court entre ces deux villes
en utilisant l'un des deux algorithmes : Dijkstra ou Bellman-Ford. Le chemin le
plus court trouvé doit être affiché, ainsi que la distance totale parcourue.

2 Exemple de graphe pondéré pour le réseau routier

marocain :

21
Figure 9 : Graphe de réseau routier marocain

22
 3 Résolution du problème de plus court chemin :
- Voici l'exécution des algorithmes de Dijkstra et de Bellman-Ford pour trouver le
chemin le plus court de Mohammedia vers les autres villes dans le graphe donné :

Figure 10 : La résolution de problème

23
 Conclusion
L'algorithme de Bellman-Ford, développé par Richard Bellman, a
révolutionné la façon dont nous abordons le problème du plus court
chemin dans les graphes pondérés. Son utilisation de la programmation
dynamique offre une approche élégante pour traiter les cycles
absorbants, rendant l'algorithme adaptable à une variété de situations.
Cependant, sa complexité temporelle plus élevée le rend moins
efficace que l'algorithme de Dijkstra dans de nombreux cas, en
particulier pour les graphes de grande taille. Il est donc crucial de
choisir judicieusement l'algorithme en fonction des caractéristiques
spécifiques du graphe et des contraintes de performance de
l'application. En définitive, bien que l'algorithme de Bellman-Ford
soit moins efficace dans certains scénarios, sa polyvalence et sa
capacité à traiter les cycles absorbants en font un outil précieux dans la
boîte à outils des algorithmes de plus court chemin.

24