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
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