TP8 .pdf


Nom original: TP8.pdf

Ce document au format PDF 1.5 a été généré par TeX / pdfTeX-1.40.14, et a été envoyé sur fichier-pdf.fr le 10/12/2017 à 22:48, depuis l'adresse IP 83.201.x.x. La présente page de téléchargement du fichier a été vue 231 fois.
Taille du document: 102 Ko (2 pages).
Confidentialité: fichier public


Aperçu du document


Universit´e d’Aix-Marseille
Algorithmique

L2 Informatique - Math´ematiques 2017/2018

TP 8 : algorithme de Bellman-Ford
Le fichier graphe1.txt contient la description d’un graphe orient´e pond´er´e, selon le mˆeme
format que celui utilis´e au TP pr´ec´edent :
— la premi`ere ligne contient le nombre de sommets du graphe
— la seconde ligne contient le nombre d’arcs du graphe
— chaque ligne suivante d´ecrit un arc sour la forme : sommet1, sommet2, poids
6
10
1 0
1 2
2 4
2 5
3 2
3 0
4 0
4 1
5 0
5 3

-2
-6
-3
-1
8
3
3
10
7
-4

Nous reprenons ´egalement la structure de graphe d´efinie au TP pr´ec´edent.
´
1. Ecrivez
la fonction void BellmanFord(int t, GRAPHE G) qui prend en entr´ee le
num´ero du sommet cible et affiche les triplets de la forme sommet distance premier
pour tous les sommets du graphe, o`
u distance est la distance `a la cible t et premier
est le premier sommet d’un chemin optimal.
Pour le graphe donn´e en exemple et t=0, vous devez obtenir :
0
1
2
3
4
5

0 -1
-8 2
-2 5
3 0
2 1
-1 3

Vous pourrez utiliser des variables int dist[NB SOM MAX],premier[NB SOM MAX] pour
stocker ces informations. A l’initialisation,
— dist[v]=INT MAX sauf dist[t]=0
— premier[v]=-1.
Vous pourrez utiliser la formule de mise `a jour suivante :
dist[v] = min(dist[v], minv0 ∈Adj[v] poids(v, v 0 ) + dist[v 0 ])
qui utilise la liste d’adjacence de v. Attention : si dist[v] contient la valeur INT MAX,
dist[v]+1 est un nombre n´egatif !
1

2. Modifiez la fonction pr´ec´edente pour qu’elle d´etecte l’existence ´eventuelle de cycles
n´egatifs. On supposera que tous les sommets sont reli´es `a t. Pour cela,
(a) vous effectuerez G.nbSommets mises-`a-jour de la variable dist ;
(b) `
a l’avant-derni`ere ´etape, vous stockerez les valeurs de dist dans un tableau dprec ;
(c) le graphe contient un cycle si et seulement si, `a la fin de l’ex´ecution de l’algorithme,
il existe un indice v pour lequel dist[v]!=dprec[v] ;
(d) ´ecrivez une fonction void rechercheCycleNeg(int v, int premier[]) qui recherche un cycle en partant de v. Indication : instanciez un tableau t avec la valeur
-1 ; remplissez le tableau par t[v]=premier[v] ; v=premier[v] jusqu’`a tomber
sur une case qui ne contient pas -1 : vous avez alors un d´epart du cycle.

2


Aperçu du document TP8.pdf - page 1/2

Aperçu du document TP8.pdf - page 2/2




Télécharger le fichier (PDF)


TP8.pdf (PDF, 102 Ko)

Télécharger
Formats alternatifs: ZIP



Documents similaires


tp8
theorie de graphe
theorie des graphes
fiches revision spe tes1 et tes2 bac 2011
sujetprojetalgoiv2012 2013
serie d exercices graphes bac eco gestion 1

Sur le même sujet..