Cols des Pyrénées
consigne:
On voudra représenter les routes entre les cols de la chaîne de montagne des
Pyrénées dans un graphe implémenté avec les structures Mat et Brin , et
déterminer le chemin permettant de passer d'un col à un autreen minimisant
le dénivelé. Les dénivelés seront représentés par des poids positifs lorsqu'il y a
un dénivelé positif, négatif sinon. On pourra par exemple se servir de cette
page et de Wikipedia.
que fait le programme et son fonctionnement :
Ce programme permet de trouver le chemin le plus court entre plusieurs cols.
Pour réaliser cela, nous avons d'abord utilisé la méthode des brins qui permet
de créer des arêtes entre deux sommets. Pour savoir d'où part l'arête, on
utilise un brin négatif et positif pour la cible. Grâce à cela, on peut créer une
matrice où l'on va trouver le poids, négatif ou positif, le sommet de destination
et le sommet de départ. Enfin, pour résoudre le problème du chemin
permettant de passer d'un col à un autre tout en minimisant le dénivelé, il faut
minimiser le dénivelé montant car, si on a deux chemins pour arriver à un col,
plus on fait de dénivelé positif, plus on aura de dénivelé négatif car, dans tous
les cas, si un chemin mène au même col, ils seront à la même hauteur. Donc,
pour vérifier tout cela, on ne va pas faire attention au dénivelé négatif (on va
les mettre à 0 dans Dijkstra, par exemple -6 sera égal à 0). Ainsi, on va utiliser
Dijkstra car, vu qu'on n'aura pas à traiter de poids négatif, il sera plus rapide
que Bellman-Ford.
les structures:
Tout d'abord, nous allons parler des structures, car c’est grâce à elles qu’on a
pu créer une matrice. Nous utiliserons la méthode Brin pour créer des liens
entre deux sommets, afin de pouvoir les relier, connaître la direction d’une
arête et son poids.
Premièrement, nous avons la structure le_tuple, qui stocke le poids de l'arête et
le brin qui va être utilisé.
Deuxièmement, Strand permet de stocker le sommet et tous les brins positifs
et négatifs avec leur poids, qui lui sont associés dans une liste ,next de type
le_tuple.
Troisièmement, StrandGraph : dans cette structure, on va retrouver la liste des
sommets , la liste des sommets et leurs brins, le nombre de sommet .
les fonctions :
creerStrandGraph : Cette fonction crée et initialise un grape avec un nombre
spécifié de sommets. Elle alloue de la mémoire pour les sommets et les brins,
et initialise les brins à INT_MAX.
libererStrandGraph : Libère la mémoire allouée pour un graphe, y compris les
listes de brins et de sommets.
ajouterBrin : Ajoute un brin entre deux sommets avec un poids donné dans
un graph.
creerGraphe : Crée une matrice d'adjacence avec un nombre donné de
sommets, alloue de la mémoire et initialise les valeurs de cette matrice à
INT_MAX.
afficherMatriceAdjacence : Affiche la matrice d'adjacence d'un graphe. Les
éléments de la matrice sont affichés comme 'INF' s'ils sont égaux à INT_MAX,
sinon leur valeur numérique est affichée.
libererMatriceAdjacence : Libère la mémoire allouée pour la matrice
d'adjacence.
la_destination : Trouve et retourne le sommet cible d'un brin donné dans un
graph qui utiliser brin.
dijkstra : Implémente l'algorithme de Dijkstra pour trouver le chemin le plus
court entre un sommet de départ et un sommet d'arrivée dans un graphe. La
fonction affiche également le chemin optimal et son coût.
afficher_StrandGraph_matrice_resulta_dijkstra : Affiche les détails du graph,
y compris les sommets, les brins, et leur poids. Elle crée également une matrice
d'adjacence pour le graphe, l'affiche, et exécute l'algorithme de Dijkstra pour
trouver un chemin optimal.
