Skip to topic | Skip to bottom
Home
Minfo
Minfo.ParallTDM7r1.10 - 23 Nov 2012 - 08:04 - LaurentPellegrinotopic end

Start of topic | Skip to actions

Algorithme du plus court chemin

Nous allons implémenter une version du calcul du plus court chemin basée sur l'algorithme de Floyd-Warshall. Ce calcul sera de type all-pairs c'est à dire que le résultat final donnera le plus court chemin (en nombre de sauts) entre n'importe quelle pair de points.

Le principe de l'algorithme est le suivant :

  • On considère un graph orienté dont les arrêtes ont un poids strictement positif entier
  • Le graph contiendra n sommets tel que n=2^k
  • Ce graph est représenté par une matrice A
  • Cette matrice A est telle que
    • aij = 0 si i = j
    • aij = poids de (i,j) si il existe une arrête reliant i et j
    • aij = 0 sinon
  • Il produira en sortie une matrice D de taille n x n dont les éléments dij représentent la distance du sommet i au sommet j

Le fonctionnement de l'algorithme est :

  • Prendre la matrice A et la transformer en matrice d'adjacence W telle que
    • wij = 0 si i = j
    • wij = poids de (i,j) si il existe une arrête reliant i et j
    • wij = +inf sinon
  • Calculer W^n en remplaçant dans la multiplication classique de matrice l'opération de multiplication par une addition et l'opération de somme par le minimum
  • Le résultat final donne le coût du plus court chemin pour n'importe quelle pair de sommets.

Exemple : À partir du graph représenté ci-dessous

* graph.jpg:
graph.jpg

on construit la matrix A suivante

  0 1 2 0 
  0 0 0 1
  0 3 0 6
  0 0 0 0

puis la matrice W

  0    1    2    +inf
  +inf 0    +inf 1
  +inf 3    0    6
  +inf +inf +inf 0

et donc W^2 (et au final W^4)

  0    1     2    2
  +inf 0     +inf 1
  +inf 3     0    4
  +inf +inf +inf  0

Grâce à cette matrice, on peut voir que le coût depuis D vers n'importe quel autre sommet est infini car il n'y pas de chemin. Pour aller de A vers D, le coût sera de 2 (A->B->D).

A rendre

La date de remise du projet est le 16 Décembre 2012 à 23h55 sur J@lon. Les contraintes suivantes sont à respecter
  • Un unique fichier nom-Floyd-Warshall.c où nom doit être remplacé par votre nom
  • Ce programme devra utiliser MPI pour la distribution du calcul, et openMP pour la parallélisation
  • Il devra prendre comme paramètre un fichier au format texte contenant la matrice A (poids séparés par des espaces, une ligne du fichier par ligne de matrice).
  • Il affichera la matrice de plus court chemin au même format que celui d'entrée (on mettra -1 pour indiquer l'absence de chemin), à l'exception de toute autre sortie.
  • Chaque valeur dans la matrice de sortie sera séparé du suivant par un unique espace, pas d'alignement de données n'est demandé
  • Le processus seront organisés en anneau et le programme doit pouvoir traiter le cas où la matrice a plus de lignes/colonnes qu'il n'y a de machines disponibles

to top

I Attachment sort Action Size Date Who Comment down
graph.jpg manage 10.7 K 27 Oct 2008 - 17:09 FabriceHuet  
mat2_1 manage 0.1 K 08 Dec 2009 - 10:34 FabriceHuet  
result2_1 manage 0.1 K 08 Dec 2009 - 10:34 FabriceHuet  

You are here: Minfo > ParallRepa > ParallTDM7

to top

Copyright © 1999-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding WIKIDeptinfo? Send feedback