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:

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

• 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