Philippe Augerat
Le problème de plus court chemin entre deux sommets dans un graphe est un problème classique et important en optimisation combinatoire. Il apparaît en tant que tel ou comme sous problème de problèmes plus complexes, en particulier les problèmes de routages d'information ou de biens. Soit parce que le graphe est très gros, soit parce que le calcul de plus court chemin sera répété un grand nombre de fois, il est important d'optimiser ce calcul.
Le problème se formule ainsi. Étant donné un graphe orienté à n sommets et un coût 
associé à chaque arc (i,j). La taille d'un chemin 
est la somme des coûts des arcs 
.
On distingue deux problèmes particuliers: celui de l'arborescence des plus courts chemins à partir d'un sommet fixé et celui du calcul de plus court chemin entre toutes les paires de sommets du graphe.
Plusieurs algorithmes sont proposés dans la littérature. Pour le premier problème, les algorithmes les plus connus sont Dijkstra dans le cas où les arcs ont un coût positif et Bellman-Ford dans le cas général (mais sans cycle de coût négatif). Ces algorithmes sont de type produit itéré, relativement faciles à paralléliser et à étendre au problème "toutes paires".
Un autre algorithme est spécialement adapté au cas "toutes paires". Il s'agit de l'algorithme de Floyd-Warshall que l'on vous demande de programmer.
Si on note 
le plus court chemin entre les sommets i et j parmi les chemins n'utilisant que des sommets dans l'ensemble 1,..,k, on peut déduire de , 
et 
la valeur de 
par la formule :
Posons 
si (i,j) appartient au graphe et 
sinon.
L'algorithme correspondant calcule les plus courts chemins entre toutes les paires de sommets du graphe.
floyd(x)
{
for (k=1;k<=n;k++)
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
x[i][j][k]= min(x[i][j][k-1],x[i][k][k-1]+x[k][j][k-1]);
}
On utilisera les données suivantes : une matrice de taille nxn générée de manière aléatoire et p<n processeurs.
On suivra les indications générales de la feuille de présentation des mini-projets.
Références : "Introduction to parallel computing", V. Kumar, A. Grama, A. Gupta, G. Karypis