home	accès étudiants

Plus courts chemins

Exercice 1

Un étudiant d'informatique souhaite voir le soleil de minuit sur les fjords de Norvège. Il décide donc de se rendre à Rana, charmante petite ville située à proximité du cercle polaire, sur la côte norvégienne. Après avoir fait le tour de quelques agences de voyage, il a recensé plusieurs connexions aériennes possibles. Il les a représenté à l'aide du graphe suivant.

Les valeurs sur les arcs correspondent au temps nécessaire pour parcourir ces arcs. Notre voyageur ne possédant qu'un faible nombre de jours de vacances, nous allons l'aider à déterminer le chemin le plus rapide pour aller de Paris à Rana, en utilisant l'algorithme de Dijkstra.

Exercice 2

Avertissement : toute rassemblance avec des événements existants ou ayant existé ne peut être que le fruit du hasard. L'expression « faire son beurre » n'a pas son origine ici.

L'histoire se passe dans un ensemble de sept pays imaginaires : Pays-Bas (P), Belgique (B), Allemagne (A), Suisse (S), Italie (I), Espagne (E) et France (F). Dans chacun de ses pays le beurre a un prix différent : certains de ces pays surproduissent, d'autres doivent importer. Chaque pays passe un accord commercial avec chacun de ses voisins fixant des aides pour l'exportation vers des pays déficitaires et des taxes pour l'exportation vers des pays surproducteurs. Ceci peut se résumer dans le tableau suivant, les coûts étant donnés en centaines d'euros par tonne. Les taxes sont en noir, les aides en rouge. S'il n y a ni aide ni taxe, on supposera qu'il n'y a pas d'exportation possible.

Par ailleurs le transport du beurre coûte lui-même un certain prix, précisé dans le tableau suivant et exprimé dans la même unité.

1. Modéliser le problème sous forme d'un problème de plus court chemin dans un graphe.
2. Résoudre le problème d'exportation du beurre des Pays-Bas vers l'Espagne. Que remarque-t-on ?
3. Que se passe-t-il si la commission des sept décide de réduire à 10 l'aide à l'exportation de la France vers l'Allemagne ?