Exercice suivant
Le chemin le plus court
Question posée à l'examen écrit du 11 octobre
1999
Soit un graphe avec 4 noeuds (1,2,3,4), avec des arcs pondérés:
Les arcs sont:
| Départ |
Arrivée |
Distance |
| 1 |
2 |
1 |
| 2 |
3 |
1 |
| 3 |
4 |
1 |
| 1 |
3 |
10 |
| 2 |
4 |
100 |
| 4 |
3 |
1000 |
Pour trouver les "distances" correspondant aux chemins les plus courts entre
le noeud 1 et tous les autres noeuds, exécutez l'algorithme suivant:
-
Soit une liste L et une liste A, toutes deux initialement vides.
-
Ajoutez à la liste L la paire (1;0) pour le noeud 1 et la "distance"
0.
Ajoutez pour chaque arc qui lie les noeuds x et y avec une "distance" z le
triplet (x;y;z) à la liste A.
-
Retirez la paire (x;y) avec le deuxième élément (y)
le plus petit de la liste L.
-
Pour chaque paire (x;y) avec le deuxième élément (y)
le plus petit de la liste L, retiré à l'étape 3, faites
ce qui suit:
-
Pour chaque arc (x,a,b) qui lie le noeud x à a avec une distance b
ajoutez la paire (a;y+b) à la liste L.
-
Retirez (x,a,b) de A
-
Pour chaque paire (x;y) dans L: S'il existe une paire (x;z) dans L avec z
plus petit ou égal à y effacez (x;y) de L.
-
Continuez en 3 tant qu'il y a encore des éléments dans A
Donnez le contenu de A et de L après chaque pas.
Exercice suivant
Site Hosting: Bronco