Exercice suivant

Le chemin le plus court

Question posée l'examen écrit du 30 juin 1999

Imaginez un graphe orienté qui est donné par sa matrice de connectivité:

		sommets d'arrivée
		1	2	3	4	5	6	7
sommets de départ	1		x		x
	2			x
	3					x
	4							x
	5						x
	6							x
	7

1. Dessinez ce graphe
2. Trouvez maintenant le chemin le plus court entre les noeuds 1 et 6. Pour ça vous avez besoin d'une file d'attente FIFO permettant de stocker des chaînes Li. Chaque Li=(Vi,1,...,Vi,n_i) contient une séquence de sommets. L'algorithme à utiliser pour trouver le chemin le plus court entre deux noeuds Vs et Vf est le suivant:
   1. Videz la FIFO
   2. Insérez la liste (Vs) dans la FIFO.
   3. Tirez la première liste de la FIFO. Appelez cet élément L1
   4. Si le premier noeud V1,1 contenu dans L1 est égal à Vf, affichez L1 de la fin au début: La séquence dans L1 est un chemin de longueur minimale entre Vs et Vf (il peut y en avoir plusieurs). L'algorithme est terminé.
   5. Sinon (le premier noeud V1,1 contenu en L1 n'est pas égal à Vf): visitez V1,1 de la façon suivante: Ajoutez pour chaque voisin v de V1,1 la liste résultant de (cons v L1) .
   6. Continuez avec le pas 3, tant que la FIFO n'est pas vide et le chemin le plus court n'a pas été trouvé au pas 4.

   Les limitations de cet algorithme sont claires. Il doit être possible d'atteindre Vf a partir de Vs. La solution doit donner le contenu de la FIFO à chaque étape de l'algorithme!

Solution

Exercice suivant

Site Hosting: Bronco