Floyd-Warshall

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:

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

Le projet est à déposer sur J@lon. Les contraintes suivantes sont à respecter

• Un fichier nom.c où nom doit être remplacé par votre nom et un fichier nom.txt qui indique quelles fonctionnalités vous avez implémenté.
• Ce programme devra utiliser MPI pour la distribution du calcul (circulation sur anneau), et openMP pour la parallélisation des calculs
• Il devra prendre comme paramètre un fichier bien formé 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

La note sera fonction des fonctionnalités implémentées dans la liste ci-dessous. Les points sont indiqués à titre indicatif

1. Calcul plus court chemin avec N multiple de P (15/20)
2. Gestion des matrices très grandes (+1 points)
3. Gestion du déséquilibre dans le calcul, i.e N non multiple de P (+2 points)
4. Produit de matrices non carrées, ce qui n'est pas utile ici (+1 point)
5. Gestion de N < P (+1 point)