Théorie des graphes : Ds devoir surveille algorithme de dijkstra 45 min
Télécharger PDFDevoir Surveillé – Algorithme de Dijkstra
1. Tableau des sommets et degrés
Sommet : A, B, C, D, E, F, G
Degrés : 2, 4, 5, 5, 4, 4, 2
2. Matrices associées au graphe
(a) Matrice d'adjacence M :
| 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 | 0 |
| 0 | 0 | 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 1 | 0 | 1 | 0 |
(b) Matrice M3 représentant les chemins de longueur 3 :
| 2 | 7 | 8 | 5 | 5 | 5 | 3 |
| 7 | 8 | 12 | 13 | 12 | 8 | 5 |
| 8 | 12 | 12 | 15 | 13 | 13 | 5 |
| 5 | 13 | 15 | 12 | 13 | 12 | 8 |
| 5 | 12 | 13 | 13 | 10 | 12 | 5 |
| 5 | 8 | 13 | 12 | 12 | 8 | 7 |
| 3 | 5 | 5 | 8 | 5 | 7 | 2 |
Le coefficient M31,6 = 5 indique qu'il existe 5 chemins de longueur 3 reliant le sommet A au sommet F.
Liste des chemins de longueur 3 entre A et F
A-B-C-F
A-B-E-F
A-B-D-F
A-C-D-F
A-C-E-F
3. Chaîne eulérienne dans un graphe connexe
Le graphe des voies d'accès principales est connexe et possède uniquement deux sommets de degré impair : C et D.
D'après le théorème d'Euler, ce graphe admet une chaîne eulérienne dont les extrémités sont C et D.
Cette propriété permet à un candidat de parcourir le quartier sans emprunter plusieurs fois la même voie.
Exemple de chaîne eulérienne
Un parcours possible est : C - B - E - D - F - G - D - B - A - C - E - F - C - D.
4. Application de l'algorithme de Dijkstra
Les durées des trajets entre les sommets (en minutes) sont :
| — | A | B | C | D | E | F | G |
| A | 0 | 8 | 12 | ∞ | ∞ | ∞ | ∞ |
| B | 8 | 0 | 6 | 12 | 20 | ∞ | ∞ |
| C | 12 | 6 | 0 | 20 | 24 | ∞ | ∞ |
| D | 24 | 12 | 20 | 0 | 16 | 24 | ∞ |
| E | 20 | 16 | 24 | 12 | 0 | 12 | 28 |
| F | ∞ | 28 | 32 | 24 | 16 | 0 | 4 |
| G | ∞ | ∞ | ∞ | ∞ | 28 | 4 | 0 |
L'algorithme de Dijkstra permet de déterminer le chemin le plus court de A à G.
Les étapes de l'algorithme sont :
A(0) ⇐ C(4) ⇐ E(16) ⇐ F(20) ⇐ G(28).
Chemin optimal et durée
(a) Le chemin de durée minimale pour rejoindre G depuis A est : A - C - E - F - G.
(b) La durée totale de ce trajet est de 28 minutes.
FAQ
Qu'est-ce qu'une matrice d'adjacence ?
Une matrice d'adjacence est une représentation tabulaire d'un graphe où chaque ligne et chaque colonne correspond à un sommet. La valeur à l'intersection de la ligne i et de la colonne j indique si les sommets i et j sont connectés par une arête.
Comment identifier une chaîne eulérienne ?
Une chaîne eulérienne existe dans un graphe connexe si et seulement si ce graphe possède zéro ou deux sommets de degré impair. Si deux sommets ont un degré impair, la chaîne commence et se termine à ces sommets.
À quoi sert l'algorithme de Dijkstra ?
L'algorithme de Dijkstra permet de trouver le chemin le plus court entre deux sommets d'un graphe pondéré. Il est particulièrement utile pour optimiser des trajets ou des réseaux logistiques.