Appliquer l'algorithme de Dijkstra pour trouver le plus court chemin entre 2 villes, le tableau suivant indiquant les connexions aériennes possibles entre les villes et les temps de vol en heures, correspondance incluse (ligne = ville de départ, colonne = ville d'arrivée)
|
Hambourg |
Amsterdam |
Londres |
Berlin |
Edimbourg |
Oslo |
Stockholm |
Rana |
Paris |
7 |
3 |
4 |
|
|
|
|
|
Hambourg |
|
|
|
1 |
|
|
1 |
|
Amsterdam |
2 |
|
1 |
|
|
8 |
|
|
Londres |
|
|
|
|
2 |
|
|
|
Berlin |
|
2 |
|
|
|
3 |
2 |
|
Edimbourg |
|
3 |
|
|
|
7 |
|
6 |
Oslo |
|
|
|
|
|
|
|
2 |
Stockholm |
|
|
|
|
|
2 |
|
5 |
Cet algorithme calcule les plus courts chemins d'un sommet d'un graphe orienté, appelé racine, à tous les autres sommets. Il ne s'applique que dans les cas où toutes les longueurs sont positives.
Cahier des charges :
• Vous pouvez vous servir d'un fichier d'entrée pour le graphe initial
• Vous utiliserez trois tableaux dynamiques (ou listes chaînées) :
• Le premier, indicé par les sommets, contient les distances de chaque sommet à la racine : 0 pour la racine(sommet initial), FLT_MAX (float à grande valeur) pour l'infini si ce n'est pas un successeur de la racine.
• Le second, indicé par les sommets sauf la racine, contient des noms de sommets pères (prédécesseurs). Ce tableau sert à indiquer, à la fin de l'algorithme, l'arborescence des plus courts chemins : -1 s'il n'existe aucun chemin de la racine au sommet.
• Le troisième, indicé par les sommets, indique si un sommet appartient déjà à l'arborescence des plus courts chemins en cours de construction.
• Le graphe sera codé par un tableau de listes des fils des sommets, chaque fils étant accompagné de la longueur de l'arc correspondant.
• Vous afficherez l'arborescence du plus court chemin entre la racine et les autres sommets en indiquant la longueur de chaque arête et la longueur totale minimale.
Travail à faire :
• Exécutez à la main l'algorithme de Dijkstra avec file de priorité vu en cours pour cet exemple
• Algorithme de Dijkstra à coder :
• Respectez le cahier des charges et faites une analyse descendante en y apportant des critiques (avantages, limitations ..) dans le choix des structures de données et de la programmation
• Vous fournirez au moins un fichier d'en-tête .h et deux fichiers sources .c (un pour les sous-programmes et un pour le main) commentés.
• Un exécutable adapté à l'exemple ci-dessus est demandé
|
