Université de Lorraine, U.H.P. TD#06

E.S.S.T.I.N. - 2A Màj.: 2011.03.13 11h31 / H. Nguyen-Phu

TD-S4#06 Calcul des PCCs (PLCs) des 1-graphes

selon Dijkstra, Floyd et la fermeture transitive

Objectif : Employer la représentation MAV pour calculer les Plus Courts (Longs) Chemins d’un graphe orienté ou non.

Exercice 1 - Algorithme de Dijkstra (une seule source, toutes cibles)

Hypothèse: Le graphe G orienté est évalué par des coûts positifs ou nuls (coûts>=0).

Le coût entre deux sommets <Si, Sj> est donné par la matrice Coût(i, j) des longueurs du graphe qui est la généralisation de la matrice d'adjacence booléenne. Le graphe possède n sommets. Soit un sommet s dans G.

But: On recherche un PCC de s à chacun des autres sommets.

a) Expliciter le principe algorithmique en employant la méthode vorace.

b) Ecrire l'algorithme. Analyser sa complexité et montrer que le temps d’exécution requis pour un graphe de n sommets est O(n²). Généraliser cet algorithme de Dijkstra pour toute paire de sommets et montrer que la complexité temporelle est polynomiale en O(n^3).

c) Traduction en Java avec un des jeux d’essai du cours. (cf. Dijkstra en langage C).

Exercice 2. - Autres algorithmes de calcul des PCCs

2.1 Algorithme de Floyd (tout couple de sommets - coûts quelconques)

Hypothèse: Le graphe, valué par des coûts quelconques, n'a pas de circuits ni de circuits absorbants (c'est-à-dire des circuits avec coût total < 0).

a) Compléter l'algorithme ci-dessous:

+ PROC. MAV::Floyd(D G: Graphe, D/R A: TABLEAU[1..n, 1..n] de REELS, D/R P: TABLEAU[1..n, 1..n] de ENT) {

// A matrice carrée est initialisée aux valeurs de Cout(i,j).

// P matrice carrée est telle que P = Père(i,j) s'il existe un chemin de Si vers Sj. Au départ P(i,j)=i.

// A compléter (cf. Cours manuscrit ) …

}

b) Montrer que la complexité est en O(n^3). En posant p le nombre d'arcs du graphe, comment procéder pour obtenir une complexité temporelle en O[n.p.Ln(n)] ?  Traduction en Java avec le jeu d’essai suivant:

<S1, S2> = +1; <S2, S4> = -2; <S6, S4> = -5;  <S2, S6> = +3; <S1, S3> = -2; <S3, S2> = +1;  <S3, S4> = +5; <S3, S5> = +4; <S5, S6> = -1; 

Indication:  cf. internet ou FROIDEVAUX et al. "Types de données et algorithmes" pp.477-480, Ediscience, 1994 [à consulter au CDI ESSTIN].

2.2 Notion de fermetures de graphes orientés : la fermeture transitive

Tracer le diagramme sagittal du graphe initial G dont la matrice des arcs à quatre colonnes (cf. convention du cours) est donnée par :

      {a    b     1 0} // ‘a’ <=> Sommet ‘0’ en Java etc …

      {b    c     1 0}

      {d    a     1 0}

      {d    e     1 0} // Q. : Pourquoi la 4è colonne est rempli de ‘0’ initialement ?

La fermeture symétrique du graphe ci-dessus est obtenue en transformant les arcs existants en arêtes symétriques. Déduire la nouvelle matrice d’adjacence. Conclure.

La fermeture réflexive du graphe initial ci-dessus est obtenue en reliant tout sommet à lui-même. Déduire la nouvelle matrice d’adjacence. Conclure.

La fermeture transitive d’un graphe orienté G est obtenue en construisant  un graphe G’ ayant les mêmes sommets que G et tel que, pour tous sommets s et t de G’, il existe un arc <s, t> si et seulement si il existe un chemin de s à t dans G.  Construire G’ et déduire la matrice d’adjacence.

Applications (à terminer en TPP#5 optionnel):

- Existe-t-il un chemin reliant deux sommets quelconques ‘i’ et ‘j’ d’un graphe orienté (cf. algo. de Floyd-Warshall )?

- Quel est le nombre total de chemins ayant pour longueur donnée ‘L’ du même graphe (cf. PCCs via la fermeture transitive) ?

- Comment modifier les algorithmes ci-dessus pour calculer les PLCs ?

- Comment vérifier que l’algo. du PCC via la fermeture transitive est plus régulier que celui de Floyd (ou Dijkstra généralisé) sachant que les trois sont en O(n^3) via des mesures de durées adéquates?