Description des algorithmes
Dijkstra
1. Présentation générale
L’algorithme de Dijkstra est un algorithme de recherche du plus court chemin dans un
graphe pondéré.
Il permet de calculer la distance minimale entre un nœud source et tous les autres nœuds
du graphe, à condition que les poids des arêtes soient positifs.
Cet algorithme est largement utilisé dans les réseaux de communication, notamment dans
les protocoles de routage comme OSPF (Open Shortest Path First).
2. Principe de fonctionnement
L’algorithme repose sur une approche gloutonne :
1. Initialiser la distance de la source à 0 et celle des autres nœuds à l’infini.
2. Sélectionner le nœud non encore visité ayant la distance minimale.
3. Marquer ce nœud comme visité.
4. Mettre à jour (relaxer) les distances de ses voisins.
5. Répéter les étapes jusqu’à ce que tous les nœuds soient traités.
À chaque itération, l’algorithme fige définitivement la plus courte distance du nœud
sélectionné.
4. Conditions d’application
L’algorithme de Dijkstra nécessite :
● un graphe connexe ou partiellement connexe,
● des poids strictement positifs,
● une source définie.
En présence de poids négatifs, les résultats peuvent être incorrects.
5. Structures de données utilisées
Selon l’implémentation, Dijkstra peut utiliser :
● une matrice d’adjacence (simple, mais coûteuse),
● une liste d’adjacence associée à une file de priorité (tas).
Dans ce projet, une matrice d’adjacence est utilisée pour faciliter la compréhension et
l’analyse.
6. Complexité de l’algorithme
● Temps :
○ O(V^2) avec une matrice d’adjacence
○ O((V+E)logV) avec un tas binaire
● Mémoire :
○ O(V) pour les tableaux de distances et de visites
où :
● V est le nombre de nœuds,
● E est le nombre d’arêtes.
Bellman-Ford
1. Présentation générale
L’algorithme de Bellman-Ford est un algorithme de recherche du plus court chemin dans
un graphe pondéré.
Contrairement à l’algorithme de Dijkstra, il est capable de fonctionner correctement même
en présence de poids négatifs.
Dans les réseaux de communication, Bellman-Ford est à la base de certains protocoles de
routage tels que RIP (Routing Information Protocol).
2. Principe de fonctionnement
L’algorithme de Bellman-Ford repose sur une approche itérative :
1. Initialiser la distance du nœud source à 0 et celle des autres nœuds à l’infini.
2. Répéter V−1 fois :
○ parcourir toutes les arêtes du graphe,
○ Appliquer l’opération de relaxation.
3. Effectuer une itération supplémentaire pour détecter la présence de cycles de poids
négatif.
Après V−1 itérations, l’algorithme garantit que toutes les distances minimales ont été
calculées si aucun cycle négatif n’existe.
3. Détection des cycles de poids négatif
Une des particularités majeures de Bellman-Ford est sa capacité à détecter les cycles de
poids négatifs.
● Si, après les V−1 itérations, une relaxation supplémentaire est encore possible,
● alors le graphe contient un cycle de poids négatif.
Dans ce cas, il n’existe pas de plus court chemin bien défini.
4. Conditions d’application
L’algorithme de Bellman-Ford nécessite :
● un graphe pondéré,
● une source définie,
● des poids pouvant être positifs ou négatifs.
Il est toutefois sensible aux cycles de poids négatif.
5. Structures de données utilisées
Bellman-Ford utilise généralement :
● un tableau dist[] pour stocker les distances minimales,
● une liste d’arêtes pour parcourir efficacement le graphe.
Cette structure est simple, mais implique un coût de calcul plus élevé.
6. Complexité de l’algorithme
● Temps : O(V×E)
● Mémoire : O(V)
où :
● V est le nombre de nœuds,
● E est le nombre d’arêtes.
Cette complexité explique pourquoi Bellman-Ford est plus lent que Dijkstra sur les grands
graphes.
L’algorithme A*
1. Présentation générale
L’algorithme A* (A-star) est un algorithme de recherche du plus court chemin dans un
graphe pondéré.
Il s’agit d’une amélioration de l’algorithme de Dijkstra, intégrant une fonction heuristique
afin d’orienter la recherche vers le nœud destination.
A* est largement utilisé dans :
● les systèmes de navigation,
● la robotique,
● les jeux vidéo,
● et de plus en plus dans les réseaux de communication intelligents.
2. Principe de fonctionnement
A* sélectionne les nœuds à explorer en minimisant une fonction d’évaluation :
f(n) = g(n) + h(n)
où :
● g(n) est le coût réel du chemin depuis la source jusqu’au nœud nnn,
● h(n) est une estimation heuristique du coût restant entre nnn et la destination.
À chaque étape, le nœud ayant la plus petite valeur de f(n) est exploré en priorité.
3. Fonction heuristique
La fonction heuristique joue un rôle clé dans les performances de A*.
Propriétés importantes :
● Admissible :
h(n) ≤ h∗(n) : (l’estimation ne doit jamais être plus grande que le vrai coût restant.)
● Consistante (monotone) :
h(n)≤c(n,n′)+h(n′) : L’estimation depuis n ne doit pas être plus grande que :
le coût pour aller au voisin + l’estimation depuis ce voisin
Lorsque ces propriétés sont respectées, A* garantit l’obtention du plus court chemin
optimal.
Exemples d’heuristiques :
● distance euclidienne,
● distance de Manhattan,
● estimation basée sur la latence moyenne du réseau.
4. Structures de données utilisées
A* utilise principalement :
● une liste ouverte (open list) :
contient les nœuds à explorer, généralement implémentée par une file de priorité,
● une liste fermée (closed list) :
contient les nœuds déjà explorés.
Ces structures permettent de prioriser efficacement les nœuds les plus prometteurs.
5. Conditions d’application
L’algorithme A* nécessite :
● un graphe pondéré à poids positifs,
● une heuristique bien définie,
● un nœud source et un nœud destination.
Une heuristique mal choisie peut dégrader les performances et rapprocher A* de Dijkstra.
6. Complexité de l’algorithme
La complexité dépend fortement de la qualité de l’heuristique :
● Pire cas :
O((V+E)logV) (équivalent à Dijkstra)
● Cas moyen :
significativement plus rapide si l’heuristique est pertinente
● Mémoire :
plus élevée que Dijkstra en raison des structures supplémentaires
Comparaison :
Critère Dijkstra Bellman-Ford A*
Type de graphe Pondéré Pondéré Pondéré
Poids négatifs Non Oui Non
Principe Glouton Itératif Glouton + heuristique
Heuristique Aucune Aucune Obligatoire
Calcul Distances depuis la Relaxation répétée Minimisation de
source des arêtes f(n)=g(n)+h(n)
Objectif Tous les nœuds Tous les nœuds Une destination
précise
Structures Tableau / File de Tableau / Liste File de priorité
utilisées priorité d’arêtes (open/closed list)
Complexité (O(V^2)) ou (O(V \times E)) (O((V+E)\log V)) (pire
temporelle (O((V+E)\log V)) cas)
Consommation Moyenne Faible Élevée
mémoire
Rapidité Rapide Lent Très rapide (bonne
heuristique)
Cycles négatifs Non détectés Détectés Non
Optimalité Garantie Garantie si heuristique
admissible
Utilisation réseau OSPF RIP Routage intelligent
Avantage Simple et efficace Gère poids négatifs Optimisé et ciblé
principal
Inconvénient Pas de poids Temps d’exécution Dépend de
principal négatifs élevé l’heuristique
Implementation :
1. Modélisation du réseau
1.1 Représentation du réseau
Dans ce projet, le réseau de communication est modélisé par un graphe pondéré
G=(V,E) où :
● V représente l’ensemble des nœuds du réseau
(routeurs, serveurs, stations, équipements réseau)
● E représente l’ensemble des liaisons de communication entre les nœuds
Chaque liaison est associée à un poids, représentant un coût de communication.
1.2 Poids des arêtes
Dans le cadre de ce travail, les poids des arêtes correspondent à une métrique réseau telle
que :
● la latence (en millisecondes),
● ou le coût de transmission,
● ou la charge du lien.
Pour simplifier l’étude initiale, on considère un seul critère (exemple : la latence).
Les poids sont supposés :
● positifs pour l’algorithme de Dijkstra et A*
● positifs ou négatifs pour Bellman-Ford
1.3 Type de réseau étudié
Dans cette première partie du projet, le réseau est considéré comme statique :
● la topologie du réseau est fixe,
● les poids des liens ne changent pas durant l’exécution des algorithmes.
Cette hypothèse permet de comparer les algorithmes de plus court chemin dans un
environnement contrôlé, avant d’introduire la dimension dynamique.
1.4 Objectif de la recherche de chemin
Étant donné :
● un nœud source s,
● un nœud destination d,
l’objectif est de déterminer :
● le chemin de coût minimal entre s et d,
● ainsi que la distance minimale associée.
1.5 Structures de données utilisées
Pour représenter le graphe, deux structures sont possibles :
● matrice d’adjacence (utilisée dans ce projet pour la simplicité),
● liste d’adjacence (plus efficace pour les grands réseaux).
Dans les implémentations réalisées, une matrice d’adjacence pondérée est utilisée.
2. Applications des algorithmes :
2.1 Exemple :
Noeud source = 0
Noeud destination = 5
2.2 Résultats :
Algorithme Distance Chemin Temps de Optimalité
minimale réponse du chemin
Dijkstra 7 0→1→2→4→5 1.003 secondes Garantie
Bellman-F 7 0→1→2→4→5 1.488 secondes Garantie
A* 8 0 → 3 → 4→ 5 1.027 secondes Non garantie
3. Comparaison générale :
Critère Dijkstra Bellman-Ford A*
Type de graphe Pondéré Pondéré Pondéré
Poids négatifs Non Oui Non
Principe Glouton Itératif Glouton + heuristique
Heuristique Aucune Aucune Obligatoire
Calcul Distances depuis la Relaxation répétée Minimisation de
source des arêtes f(n)=g(n)+h(n)
Objectif Tous les nœuds Tous les nœuds Une destination
précise
Structures Tableau / File de Tableau / Liste File de priorité
utilisées priorité d’arêtes (open/closed list)
Complexité (O(V^2)) ou (O(V \times E)) (O((V+E)\log V)) (pire
temporelle (O((V+E)\log V)) cas)
Consommation Moyenne Faible Élevée
mémoire
Rapidité Rapide Lent Très rapide (bonne
heuristique)
Cycles négatifs Non détectés Détectés Non
Optimalité Garantie Garantie si heuristique
admissible
Utilisation réseau OSPF RIP Routage intelligent
Avantage Simple et efficace Gère poids négatifs Optimisé et ciblé
principal
Inconvénient Pas de poids Temps d’exécution Dépend de
principal négatifs élevé l’heuristique
4. Conclusion :
4.1. Dijkstra
Dijkstra offre un excellent temps de réponse dans les réseaux statiques à
poids positifs, comme les réseaux filaires, les réseaux IP internes ou les
topologies stables.
Sa complexité temporelle est faible O(V2)) ou O((V+E)logV) avec une file de
priorité, ce qui le rend très efficace pour les réseaux de taille moyenne à
grande.
Cependant, il ne supporte pas les poids négatifs, ce qui limite son utilisation
dans des réseaux fortement dynamiques ou complexes.
Type de réseau idéal :
● Réseaux IP statiques
● Réseaux d’entreprise
● Protocoles de routage (ex : OSPF)
4.2. Bellman-Ford
Bellman-Ford est particulièrement adapté aux réseaux dynamiques ou
instables, car il gère les poids négatifs et détecte les cycles négatifs, ce qui
renforce la fiabilité du routage.
En revanche, sa complexité temporelle élevée O(V×E)O(V \times E)O(V×E)
entraîne un temps de réponse plus lent, ce qui le rend peu performant dans
les grands réseaux.
Il est donc privilégié lorsque la robustesse prime sur la rapidité.
Type de réseau idéal :
● Réseaux dynamiques
● Réseaux à coûts variables
● Protocoles simples (ex : RIP)
4.3. A*
A* est l’algorithme le plus performant en termes de temps de réponse
lorsqu’une heuristique fiable est disponible.
Il est particulièrement efficace dans les réseaux orientés vers une
destination précise, car il réduit fortement l’espace de recherche.
Sa complexité dépend de la qualité de l’heuristique, mais dans la pratique,
il est plus rapide que Dijkstra, au prix d’une consommation mémoire plus
élevée.
Type de réseau idéal :
● Réseaux intelligents
● Routage adaptatif
● Systèmes temps réel (GPS, réseaux mobiles)