Si un graphe a des cycles de poids négatif, alors formellement l'algorithme de Floyd-Warshall n'est pas applicable à un tel graphe.
En fait, pour les paires de sommets i j, entre lesquelles il est impossible d'entrer un cycle de poids négatif, l'algorithme fonctionnera correctement.
Pour les mêmes paires de sommets pour lesquels il n'y a pas de réponse (en raison de la présence d'un cycle négatif sur le chemin entre eux), l'algorithme de Floyd trouvera un certain nombre (éventuellement fortement négatif, mais pas nécessairement) comme réponse. Cependant, l'algorithme de Floyd peut être amélioré pour gérer correctement ces paires de sommets et produire par exemple \(- \infty\).
Pour ce faire, par exemple, le critère "non-existence du chemin" peut être fait. Alors, laissez l'algorithme de Floyd habituel travailler sur ce graphique. Alors il n'y a pas de plus court chemin entre les sommets i et j si et seulement s'il existe un sommet t accessible depuis i et à partir duquel j est accessible, pour lequel \(d [t][t]<0\).
De plus, lors de l'utilisation de l'algorithme de Floyd pour les graphiques avec des cycles négatifs, il ne faut pas oublier que les distances qui surviennent au cours du travail peuvent aller négativement, de manière exponentielle à chaque phase. Par conséquent, vous devez faire attention au dépassement d'entier en limitant toutes les distances à partir du bas à une certaine valeur (par exemple, \(- \infty\)).
Verbalement, la solution peut être décrite comme suit :
Une fois que l'algorithme de Floyd-Warshall a fonctionné pour le graphe d'entrée, parcourons toutes les paires de sommets \((i,j)\), et pour chacune de ces paires on vérifie, infiniment le plus court chemin de i à j est petit ou non. Pour ce faire, parcourons le troisième sommet t, et s'il s'avère être \(d[t][t] < 0\) (c'est-à-dire qu'il se situe dans le cycle de poids négatif), et il est accessible depuis i et j — alors le chemin \((i,j)\) peut être d'une longueur infinitésimale.