67 lines
2.1 KiB
Markdown
67 lines
2.1 KiB
Markdown
|
TP Graphes 4 : Plus Court Chemin et Arbre Recouvrant Minimal
|
||
|
|
============
|
||
|
|
|
||
|
|
Le TP est prévu pour être fait en utilisant le codage des graphes à l'aide de matrices d'adjacence.
|
||
|
|
Pour plus de clarté, vous pouvez utiliser une nouvelle classe, en copiant les structures et fonctions nécessaires depuis les TPs précédants.
|
||
|
|
|
||
|
|
|
||
|
|
- - - - -
|
||
|
|
Exercice 0 : Graphes valués
|
||
|
|
----------
|
||
|
|
|
||
|
|
Nous avons enrichi nos graphes avec une valuation des arêtes.
|
||
|
|
|
||
|
|
**Question :**
|
||
|
|
|
||
|
|
Comment intégrer cela à notre structure de données ?
|
||
|
|
|
||
|
|
|
||
|
|
Quel fonction(s) faut-il modifier pour prendre en compte cet enrichissement ?
|
||
|
|
|
||
|
|
**Question :**
|
||
|
|
|
||
|
|
Créez une nouvelle classe GraphesValues.java contenant la structure et les primitives nécessaires à la manipulation des graphes valués.
|
||
|
|
|
||
|
|
|
||
|
|
- - - - -
|
||
|
|
Exercice 1 : Algorithme de Dijkstra
|
||
|
|
----------
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
L'algorithme de Dijkstra renvoie deux données : la fonction d donnant la distance minimale entre la source et un sommet, et la fonction père donnant la direction à prendre pour atteindre cette distance minimale.
|
||
|
|
|
||
|
|
**Question :**
|
||
|
|
|
||
|
|
Une fonction des sommets vers un entier (ou un autre sommet) sera représentée par un tableau où la case i contient la valeur de la fonction pour i.
|
||
|
|
|
||
|
|
Nous souhaitons cependant renvoyer deux fonctions. Comment modéliser cela ?
|
||
|
|
|
||
|
|
**Question :**
|
||
|
|
|
||
|
|
Implémentez l'algorithme de Dijsktra, que je redonne ci-dessous :
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
**Question :**
|
||
|
|
|
||
|
|
Testez votre algorithme en reprenant le graphes des frontières avec des valuation de votre choix.
|
||
|
|
Vérifier à la main que l'algorithme effectue les bons calculs.
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
- - - - -
|
||
|
|
Exercice 2 : Algorithme de Prim
|
||
|
|
----------
|
||
|
|
|
||
|
|
Pour simplifier l'implémentation, on se contentera d'afficher sur la sortie standard les arêtes sélectionnées. On renverra tout de même la valuation totale de l'arbre couvrant.
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
**Question :**
|
||
|
|
Implémentez l'algorithme de Prim. Il n'y a pas besoin de modéliser l'ensemble T puisque l'on va l'afficher sur la sortie standard tout au long de l'algorithme.
|
||
|
|
|
||
|
|
**Question :**
|
||
|
|
Testez et vérifiez votre implémentation sur un exemple, au hasard le graphe des frontières.
|