(pour signaler une erreur monnerat@u-pec.fr)
Plus court chemin : algorithme de Dijkstra
L'algorihtme de Dijkstra permet de résoudre le problème des plus courts chemin dans un graphe valué positivement, c'est à dire un graphe ou chaque arête est pondéré par un nombre positif (une distance, un coût, etc ).
Un exemple concret de tel graphe est un réseau routier. Les sommets sont des villes, les arêtes des routes avec une distance. Comment calculer un plus court chemin entre deux villes données ?
Il s'agit de construire progressivement, à partir des données initiales, un sous-graphe dans lequel sont classés les différents sommets par ordre croissant de leur distance minimale au sommet de départ. La distance correspond à la somme des poids des arêtes empruntées.
Vous allez implanter l'algorithme Dijkstra. En voici une description en pseudo-code
Entrées : un graphe avec une valuation positive des arêtes, un sommet de Sorties : tableau des distances minimales de chaque sommet depuis , un tableau qui contient pour chaque sommet le sommet qui le précède dans un plus court chemin de la source à . Initialiser tous les sommets comme étant « non marqué ». Affecter la valeur à tout Tant Qu'il existe un sommet non marqué Choisir un sommet non marqué de plus petit valeur Marquer Pour chaque sommet non marqué voisin de Si Alors Fin Si Fin Pour Fin Tant Que
Un exemple pour determiner le plus court chemin de A vers J.
On marque A. On met à jour B, C, et E avec 85, 217, 173
On marque B, et met à jour F avec 85+80=165
On marque F. On met à jour I (415)
On marque E. On met à jour J (675)
On marque C. On met à jour G (403) et H (320).
On marque H. On met à jour D et J (487< 675)
On marque G.
On marque I.
On marque J
On préfere présenter les calculs sous forme d'un tableau. Chaque ligne représente une nouvelle étape.
à B | à C | à D | à E | à F | à G | à H | à I | à J | |
---|---|---|---|---|---|---|---|---|---|
A | 85 | 217 | ∞ | 173 | ∞ | ∞ | ∞ | ∞ | ∞ |
B(85A) | - | 217 | ∞ | 173 | 165 | ∞ | ∞ | ∞ | ∞ |
F(165B) | - | 217 | ∞ | 173 | - | ∞ | ∞ | 415 | ∞ |
E(173A) | - | 217 | ∞ | - | - | ∞ | ∞ | 415 | 675 |
C(217A) | - | - | ∞ | - | - | 403 | 320 | 415 | 675 |
H(320C) | - | - | 503 | - | - | 403 | - | 415 | 487 |
G(403C) | - | - | 503 | - | - | - | - | 415 | 487 |
I(415F) | - | - | 503 | - | - | - | - | - | 487 |
J(487H) | - | - | 503 | - | - | - | - | - | - |
D(503H) | - | - | - | - | - | - | - | - | - |
Remarque La construction de ce tableau donne non seulement la distance minimale de la ville A à la ville J mais aussi le chemin à suivre (J - H - C - A) ainsi que toutes les distances minimales de la ville A aux autres villes rangées par ordre croissant.
Votre travail
Vous disposez d'une archive qui permet de représenter un graphe avec des fonctions d'entrées/sorties déjà écrites qui reprennent celles du tp précedent.
Le format texte d'importation est le suivant :
Sommets 6 Oriente 0 A 0 1 2 A 0 2 3 A 1 2 1 A 1 4 4 A 2 3 2 A 4 5 2 A 3 5 10
Le dernier nombre lors de la déclaration d'une arête représente sa valeur
Votre travail consiste à écrire la fonction dijkstra
#ifndef _DIJKSTRA_H #define _DIJKSTRA_H #include "graphe.h" void dijkstra(graphe G,int s_init,int *preced,int *distance); /* en entrée : * G le graphe * s_init le sommet de départ * en sortie : * distance le tableau des distance calculées * depuis s_init vers tous les sommets du graphe * preced le tableau des precdents de chaque sommet * dans un chemin le plus court depus s_init */ #endif
Remarques
Dans les sources, une constante INFTY
représente la valeur . Vou pouvez faire des calculs
avec cette valeur (addition et test d'infériorité avec les fonctions plus
et inf
)
Applications
Amsterdam Hambourg 2 Amsterdam Londres 1 Amsterdam Oslo 8 Berlin Amsterdam 2 Berlin Oslo 3 Berlin Stockholm 2 Hambourg Berlin 1 Hambourg Stockholm 1 Edimbourg Amsterdam 3 Edimbourg Oslo 7 Edimbourg Rana 6 Londres Edimbourg 2 Paris Amsterdam 3 Paris Hambourg 7 Paris Londres 4 Oslo Rana 2 Stockholm Oslo 2 Stockholm Rana 5
Donnez pour chaque ville la distance minimale par rapport à Paris, ainsi qu'un chemin correspondant.
Dans l'épisode 23 de la saison 3 de Numb3rs, intitulé Money for Nothing, un camion contenant de l'argent et des médicaments a été attaqué.
Comme les voleurs souhaitent quitter la ville (Los Angeles) le plus rapidement possible, et qu'ils ont prémédité leur coup, le héros (Charlie) essaye de déterminer le plus rapide des chemins possibles, reliant le lieu de l'embuscade à la porte de sortie de la ville la plus proche. L'embuscade a eu lieu dans le noeud (croisement) supérieur gauche de l'image ci-dessous, et la sortie est le noeur inférieur droit ;
Les valeurs sur les arcs/flèches représentent les temps nécessaires pour rejoindre chaque croisement.
Calculez tous les chemins minimaux.