Cette page présente plusieurs exercices corrigés sur le problème de plus court chemin. Les exercices portent principalement sur le chemin le plus court pour une source et le chemin le plus court à partir de plusieurs sources.
Exercice 1
| A | B | C | D | E | |
| A | 1h30 | 2h00 | 2h15 | ||
| B | 1h40 | 3h00 | |||
| C | 2h20 | 2h55 | |||
| D | 3h20 | 1h05 | |||
| E | 2h25 | 3h10 | 1h10 |
Il suffit de tracer le graphe, dont les sommets sont les villes et les arcs les itinéraires de la compagnie, valorisé à chaque arc la longueur du vol correspondant. Un algorithme de chemin le plus court résout alors le problème.
Pour prendre en compte la durée des escales, deux méthodes sont possibles : Editer l’algorithme précédent, en incluant dans les arcs le coût d’escale OU : chaque sommet est dupliqué ; un arc entre eux est l’escale de la ville correspondante.
Exercice 2
Nous voulons construire une nouvelle usine dans le réseau suivant, les nœuds sont des lieux et les liens représentent les coûts pour envoyer de l’énergie d’un endroit à un autre :
Basé sur l’algorithme de Dijkstra, proposez une méthode pour trouver le meilleur endroit pour construire l’usine, puis résolvez le problème avec votre méthode. Résolvez le problème avec l’algorithme de Floyd-Warshall.
Nous devons calculer Dijkstra pour chaque nœud (au nœud source). Une fois l’arborescence des chemins créée, additionnez le coût de tous les chemins de n’importe quel nœud au nœud source (additionnez le dernier tableau de chemins les plus courts). Le meilleur endroit est le poids total minimum de toutes les occurrences de Dijkstra. Avec Floyd-Warshall, la matrice de pseudo-fermeture contient tous les tableaux, additionnez simplement les entrées de chaque tableau et trouvez le minimum.
Exercice 3
Un robot se déplace dans l’environnement suivant. Il commence à partir du nœud étiqueté début et doit atteindre le nœud étiqueté fin. L’environnement est continu et l’échelle est fournie sur la figure. Considérant que le robot est un point, quel est le chemin le plus court du début à la fin.
Calculer la distance euclidienne entre les nœuds. Dessinez le graphique et appliquez l’algorithme de Dijkstra pour trouver le chemin le plus court du nœud Star au nœud End. Dessinez ensuite le chemin sur la figure.
Shortest path | Start | 1 | 2 | 3 | End |
Init | 0 | inf | inf | inf | inf |
Start | – | sqrt 5 | sqrt 29 | inf | inf |
1 | – | – | sqrt 29 | sqrt 5+ sqrt 26 | inf |
2 | – | – | – | sqrt 5+ sqrt 26 | sqrt 29 + sqrt 17 |
3 | – | – | – | – | sqrt 29 + sqrt 17 |
Le plus court chemin est Start-2-End.
Exercice 4
Considérant le graphique de l’exercice 1, les arêtes sont dirigées de gauche à droite (ou de haut en bas) et les poids sont diminués de 4. Comment trouver un chemin minimal de A à F ? Résoudre.
Exercice 5
(a) Calculez le chemin le plus court de s à tous les autres sommets en utilisant l’algorithme de Dijkstra. Déterminez l’arborescence des chemins les plus courts.
(b) L’arbre du plus court chemin est-il unique ?
(c) Modifiez maintenant le poids de l’arête (3, 4) en −2. Montrez que l’algorithme de Dijkstra ne fonctionne pas dans ce cas.
(a) La solution est donnée par l’image suivante. Les nombres à côté des sommets sont les distances au sommet de départ et barrer un nombre signifie qu’il y a eu une mise à jour. Les nombres dans les carrés indiquent les distances finales (distances les plus courtes).
(b) Aucun arbre de plus court chemin n’est unique. En remplaçant l’arête (s, 3) par l’arête (1, 2) on obtient un autre arbre des plus courts chemins.
(c) L’algorithme de Dijkstra donnera la même solution que dans la partie (a) bien que le chemin (s, 1, 2, 3, 4) (dist 5) ait une distance plus courte que le chemin (s, 1, 4) ( dist 6). Voici ce qui se passe : après avoir visité les sommets s, 1, 2, l’algorithme recherchera le chemin le plus court vers un sommet non encore visité. Ce sera le sommet 4 avec la distance 6. Après avoir visité le sommet 4, l’algorithme ne fera pas de mise à jour sur le sommet 4 car il a déjà été visité et pour cette raison ne trouve pas le chemin le plus court (distance 5).
Exercice 6
Un homme doit transporter un loup, une chèvre et un chou de l’autre côté d’une rivière. Il a un bateau pour le faire mais il est si petit qu’il ne peut emporter qu’une seule des trois choses avec lui à chaque fois. Est-il possible d’amener les trois choses de l’autre côté de la rivière en toute sécurité ? Notez que le loup et la chèvre ou la chèvre et le chou ne doivent jamais être du même côté de la rivière sans surveillance de l’homme. Au moins le loup n’est pas végétarien et n’aime pas manger du chou.
Nous construisons un graphe pour ce problème où chaque état légal est représenté par un sommet dans le graphe et recherchons un chemin le plus court dans ce graphe. Soit donc S = {M,W,G, C} où M,W,G, C sont l’homme, le loup, la chèvre et le chou.
Un état pour ce problème est une paire (X, Y ) où {X, Y } est une partition de S. Les éléments de X sont toujours du côté de départ de la rivière et les éléments de Y sont déjà de l’autre côté. Un état est un état légal si W,G ∈ X, Y ⇒ M ∈ X, Y et G, C ∈ X, Y ⇒ M ∈ X, Y, vous ne pouvez pas laisser seuls le chou et le loup ou la chèvre et le chou sans surveillance.
Construisons maintenant un graphe G = (V, E) qui a un sommet pour chaque état légal de ce problème. Nous avons l’arête dirigée (v1 , v2 ) ∈ E si nous pouvons passer de l’état v1 = (X1 , Y1 ) à l’état v2 = (X2 , Y2 ) en un seul voyage en bateau sur la rivière. Toutes les arêtes ont le poids ce = 1. Maintenant, le problème peut être résolu en calculant le chemin le plus court de l’état (sommet) s = (S, -) à l’état (sommet) t = (-, S). Nous obtenons 7 comme la solution du chemin le plus court.
Exercice 7
Considérez la modification suivante de l’algorithme de Dijkstra pour travailler avec des poids négatifs : w(e) = c. Alors pour toutes les arêtes f dans E on pose w’(f) := w(f) – c. Alors G’= (V,E,w’) n’a pas de poids négatifs. Cette version de l’algorithme fonctionne-t-elle correctement sur ce type de graphe ? Prouvez votre affirmation.
Maintenant, nous affirmons que l’algorithme ne fonctionne pas correctement sur G’ car cette modification ne conserve pas la propriété du chemin le plus court, c’est-à-dire que (-c) est un nombre positif, donc vous l’ajoutez n fois pour un n-chemin. Le contre-exemple suivant le prouve :
