(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.

• Au départ, on considère que les distances de chaque sommet au sommet de départ sont infinies, sauf pour la sienne qui est nulle.
• A chaque itération, on choisit dans les sommets qui ne font pas partie du sous-graphe jusqu'alors calculé un sommet pour lequelle la distance est minimale.
  • On le rajoute au sous-graphe : le calcul de sa distance minimale par rapport au sommet de départ est terminé.
  • On met à jour les distances de ses voisins en passant par lui si cela les diminue (relaxation).
• On s'arrête lorsque tout les sommets font partie du sous graphe, ou lorsque le sommet d'arrivée est atteint si on s'interesse uniquement à un trajet entre deux sommets.

Vous allez implanter l'algorithme Dijkstra. En voici une description en pseudo-code

Entrées : $G=(S,E)$  un graphe avec une valuation positive $v$ des  arêtes, $s_{\text{deb}}$ 
un sommet de $S$

Sorties : $D$  tableau des distances minimales de chaque sommet depuis 
$s_{\text{deb}}$, un tableau $P$  qui contient pour chaque sommet le sommet  qui le précède dans un plus court chemin de la source à $s_{\text{deb}}$. 
Initialiser tous les sommets comme étant « non marqué ». Affecter la valeur $\infty$  à tout $D$
$D\left(s_{\text{deb}}\right)=0$
Tant Qu'il existe un sommet non marqué
    Choisir un sommet $a$ non marqué de plus petit valeur $D$
    Marquer $a$
	Pour chaque sommet $b$ non marqué voisin de $a$
		Si $D\left(b\right)>D\left(a\right)+v\left(a\text{,}b\right)$ Alors
			$D\left(b\right)=D\left(a\right)+v\left(a\text{,}b\right)$
			$P\left(b\right)=a$
		Fin Si
    Fin Pour
Fin Tant Que

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 $\infty$. Vou pouvez faire des calculs avec cette valeur (addition et test d'infériorité avec les fonctions plus et inf)

Applications

1. On donne la liste des villes suivantes et des distances correspondantes

   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.

2. 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 ;

   • une flèche représente une rue à sens unique,
   • un arc représente une rue empruntable dans les deux sens.

   Les valeurs sur les arcs/flèches représentent les temps nécessaires pour rejoindre chaque croisement.

   
   
   

   Calculez tous les chemins minimaux.