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 une suite G[n] de graphes indexés par les entiers. L'ensemble des sommets du graphe G[n] est constitué des entiers {0,1,...,n-1}. On dit que (x,y) est une arête de G[n] si et seulement s'l existe un diviseur premier p de n - 1 tel que y soit égal à p*x modulo n , et le poids de cette arête est p.
Ecrire une fonction MonGraphe(int n) pour construire la matrice de pondération du graphe G[n].
Implanter une fonction int Dijstra(graphe g, int org, int but) qui retourne la valeur du plus court chemin du sommet org au sommet but. Montrer que pour tout entier n, les sommets 1 et n-1 sont nécessairement dans la même composante connexe. 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 la longueur 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.