Scribd
Importer
47 vues8 pages

Chapitre4 (Algorithme de Dijkstra)

Le document présente le problème du plus court chemin en théorie des graphes, en se concentrant sur l'algorithme de Dijkstra. Cet algorithme est utilisé pour déterminer le chemin le moins coûteux entre deux sommets dans un graphe pondéré, avec des applications dans les réseaux informatiques. Un exemple pratique est fourni pour illustrer l'application de l'algorithme dans un contexte de frais de déplacement entre des villes.

Transféré par

SIDIBÉ Gaming
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
47 vues8 pages

Chapitre4 (Algorithme de Dijkstra)

Le document présente le problème du plus court chemin en théorie des graphes, en se concentrant sur l'algorithme de Dijkstra. Cet algorithme est utilisé pour déterminer le chemin le moins coûteux entre deux sommets dans un graphe pondéré, avec des applications dans les réseaux informatiques. Un exemple pratique est fourni pour illustrer l'application de l'algorithme dans un contexte de frais de déplacement entre des villes.

Transféré par

SIDIBÉ Gaming
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

TechnoLAB - ISTA Année 2023-2024

L2 AP
Théorie de graphe

Chapitre 4. Problème du plus court chemin (Algorithme de Dijkstra)

Figure 1 – Edsger Wybe Dijkstra né à Rotterdam le 11 mai 1930 et mort à Nuenen le 6 août
2002, est un mathématicien et informaticien néerlandais du xxe siècle

Ce problème intervient principalement dans le fonctionnement des routeurs d’un réseau


informatique (protocoles de routage).

1
Figure 2

La recherche du plus court chemin est analogue à la recherche du plus long chemin.
Définition 1.
Soit G = (X, U ) un graphe valué (ponderé), l’interprétation de la valeur de chaque arc peut
être : coût de transport, distance, dépense de construction, temps nécessaire de parcours, etc.
— La longueur d’un chemin entre deux sommet x et y dans un graphe valué est :
X
longChemin(x, y) = f (u)
u∈ch

f (u) est la fonction qui fournit la valeur de l’arc u


— La distance, notée dG(x, y), entre deux sommets d’un graphe G est la longueur du plus
court chemin entre les extrémités x et y. S’il n’y a pas de chemin entre x et y on considère
que dG(x, y) = ∞.

Algorithme de Dijkstra
Cet algorithme permet de trouver le plus court chemin entre deux sommets Sdeb et Sfin

Figure 3

Tel que M est la matrice des longueurs (matrice d’adjacence) dont chaque élément mi,j est
définit comme suit : 
 mij si lárc u = (xi , xj ) ∈ U

∞ si lárc u = (xi , xj ) ∈
/U


0 si i = j

2
Remarques :
1. il ne s’applique qu’aux graphes à valuations positives
2. il ne marche que pour trouver les plus courts chemins
3. pour chaque sommet dans le chemin, sauvegarder toujours le sommet précèdent

Exemple :

On se propose dedéterminer le plus court chemin dans le graphe G suivant :

Figure 4 – L’algorithme de Dijkstra permet de répondrementefficacement à ce problème.

1. La matrice des longueurs (matrice d’adjacence)

Figure 5

2. Commençons par la prmière itération

3
Figure 6 – Itération 1

3. Itération 2.

Figure 7 – Itération 2

4. Itération trois et quatre

Figure 8 – Itération 3 et 4

5. A la fin, on obtien donc le résultat suivant :

4
Figure 9 – Source : sur internet URL

Par suite, le plus court chemin est : Sdeb − b − a − c − d − df in , avec comme distance 13 !

1 Exercices
1.1 Exercice 1.
Le graphe ci-dessous indique les frais de déplacement occasionnés (péage, essence,...) pour
un trajet entre deux villes, exprimés en euro. Appliquer l’algorithme de Dijkstra à l’aide d’un
tableau pour déterminer le trajet le moins onéreux pour se rendre de Calais à Mulhouse, et
indiquer ce coût.
Corrigé : Faites minitieusement les camculs pour trouver :

Figure 10 – C : Calais L : Lille N : Nancy S : Strasbourg A : Amiens T : Troyes D : Dijon


M : Mulhouse

5
Figure 11 – Ainsi, le trajet minimal de C à M coûte 118 euros.

En utilisant python, on obtient le code suivant :

Figure 12 – Voir Franck CHEVRIER sur [Link]

6
Figure 13 – suite...

Figure 14 – Fin

7
Références
[1] Dr. N. Elamathi, R. Nithya, Une exploration des algorithmes de Dijkstra et de
Floyd dans la méthode de trafic urbain, 2022

Vous aimerez peut-être aussi