Temps : 1 séance de 3 heures.
L'algorithme Dijkstra(G,w,s) détermine les longueurs des plus courts chemins du sommet source s vers tous les autres sommets d'un graphe G dont les arêtes sont pondérées par la fonction de poids w. Pour mémoire,Algorithme Dijkstra(G, w, s)
Donnees
G : graphe;
w :fonction de ponderation;
s : sommet;
variables
E : ensemble de sommets;
x , y : sommets;
d : table des distances;
debut
E := sommet[G];
Initialiser(d);
tantque non vide(E) faire
x := ChercherMinimum(E);
E := E \ {x};
pour chaque y dans G+(x) faire
relacher(x,y,w);
fdp
tqf
retourner(d);
fin
On commence par définir un graphe aléatoire G[n,p] indexés par les entiers. L'ensemble des sommets du graphe G[n,p] est constitué des entiers {0,1,...,n-1}. La probabilité pour que (x,y)
soit une arête est p, et si (x,y) est une arête son poids est la distance de Hamming de x à y.
Ecrire une fonction int ** MonGraphe(int n) pour construire la matrice de pondération du graphe G[n].
Implanter une fonction int Dijkstra(graphe g, int org, int but) qui retourne la valeur du plus court chemin du sommet org au sommet but. Calculer expérimentalement un plus court chemin du sommet 1 au sommet n-1 dans le graphe G[n]. Modifier votre algorithme pour retourner un modèle de plus court chemin.
Implanter l'algorithme int * DijstraPlus(graphe g) qui calcule les longueurs des plus courts chemins d'origine 1. Soit t(n) le temps d'exécution de DijstraPlus(g) appliquée au graphe G[n]. Mesurer les valeurs de t(n) pour quelques valeurs de n. Commenter les résultats.
[ 4 ] Liens
Edsger Dijkstra home page une applet java