Algorithme Floyd-Warshall : guide d'entretien de codage

TL;DR: L'algorithme Floyd – Warshall calcule les chemins les plus courts de toutes les paires avec une programmation dynamique. Initialisez une matrice de distance à partir du graphique, puis pour chaque sommet intermédiaire k, mettez à jour chaque paire avec dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Il s'exécute dans le temps O(V³) et dans l'espace O(V²) et peut exposer des cycles négatifs via des entrées diagonales négatives.

Qu'est-ce que l'algorithme Floyd-Warshall ?

Floyd – Warshall est un algorithme de programmation dynamique pour les chemins les plus courts entre chaque paire ordonnée de sommets. Il fonctionne avec des graphiques pondérés orientés ou non et autorise des bords négatifs. Cependant, si un cycle de poids négatif pertinent existe, certains chemins les plus courts n'ont pas de minimum fini car le fait de parcourir le cycle à plusieurs reprises continue de réduire le coût du chemin.

L'algorithme est mémorable car il transforme un problème de chemin global en une seule décision : pour le sommet intermédiaire actuel k, le chemin le plus connu de i à j est-il meilleur tel quel, ou en passant de i à k puis de k à j ?

Comment calculez-vous la récidive ?

Définir D(k, i, j) comme la distance la plus courte de i à j dont les sommets intermédiaires ne peuvent provenir que des k premiers sommets. Un chemin autorisé le plus court soit évite le sommet k, en gardant D(k−1, i, j), soit utilise k et se divise en le meilleur chemin autorisé de i à k plus le meilleur chemin autorisé de k à j.

Cela donne la récurrence :

D(k, i, j) = min(D(k−1, i, j), D(k−1, i, k) + D(k−1, k, j))

Étant donné que l'étape k dépend uniquement des valeurs de l'étape k−1 de manière compatible, la matrice peut être mise à jour sur place. Ce raisonnement explique également l'ordre critique des boucles : k doit être la boucle la plus externe. Mettre i ou j à l'extérieur modifie l'invariant et peut utiliser de manière incorrecte des chemins partiellement autorisés.

Comment initialiser la matrice de distance ?

Créez une matrice V par V. Définissez dist[i][i] sur zéro, définissez la cellule d'un bord direct sur son poids et utilisez l'infini lorsqu'aucun bord direct n'existe. Si des bords parallèles sont possibles, conservez le plus petit poids direct. Avant d'ajouter deux distances, vérifiez que les deux sont finies afin qu'une sentinelle infinie ne déborde pas ou ne crée pas de faux candidat.

Comment retrouvez-vous Floyd-Warshall dans une interview ?

Étiquetez les lignes de la matrice comme sources et les colonnes comme destinations. Montrez la matrice initiale, puis choisissez-en une k et évaluez les cellules représentatives. Pour chaque cellule, comparez la valeur actuelle avec le parcours passant par k. Mettez à jour uniquement lorsque les deux segments sont accessibles et que la nouvelle somme est plus petite.

Vous n’avez normalement pas besoin de dessiner chaque matrice pour un grand exemple. Tracez suffisamment de cellules pour démontrer l'invariant, y compris une amélioration et une valeur inchangée. Déclarez qu'après avoir terminé k, chaque entrée de la matrice est optimale parmi les chemins dont les sommets intermédiaires sont limités à l'ensemble traité.

Quel pseudocode devez-vous écrire ?

Utilisez trois boucles imbriquées avec k à l'extérieur :

for k from 0 to V - 1:
  for i from 0 to V - 1:
    for j from 0 to V - 1:
      if dist[i][k] is finite and dist[k][j] is finite:
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Expliquez les contrôles finis et le type numérique. Dans les langages avec une sentinelle entière de grande taille, l'ajout de l'infini à une valeur négative peut sembler fini ou déborder. Une garde fait partie de l'exactitude, pas seulement un détail de mise en œuvre.

Quelles sont les complexités temporelles et spatiales ?

Les trois boucles examinent chaque combinaison de k, i et j, le temps d'exécution est donc O(V³). La matrice de distance occupe l'espace O(V²). La mise à jour sur place évite une table tridimensionnelle, tandis qu'une matrice de saut suivant ou de prédécesseur pour la reconstruction du chemin ajoute O(V²) plus d'espace.

Floyd – Warshall est souvent attrayant pour les graphes denses modestes car sa mise en œuvre est compacte et prévisible. Pour un grand graphique clairsemé avec des bords non négatifs, exécuter Dijkstra à partir de chaque source peut être plus efficace. Comparez toujours la sortie requise, la densité du graphique, les contraintes de poids et le nombre de sommets avant de choisir.

Comment reconstruire le véritable chemin le plus court ?

Les distances à elles seules ne révèlent pas la séquence des sommets. Conservez une matrice next[i][j] initialisée à j lorsqu'il existe une arête directe de i à j. Chaque fois que le routage via k améliore dist[i][j], définissez next[i][j] sur next[i][k]. Pour reconstruire un chemin, déplacez-vous à plusieurs reprises du sommet actuel vers next[current][destination] jusqu'à atteindre la destination.

Recherchez les paires inaccessibles avant la reconstruction et protégez-vous contre les cas de cycle négatif. Si une paire peut voyager vers un cycle négatif puis atteindre la destination, il n’y a pas de chemin le plus court fini à reconstruire.

Comment Floyd-Warshall détecte-t-il les cycles négatifs ?

Une fois l’algorithme terminé, inspectez la diagonale. Une valeur dist[v][v] < 0 prouve qu'un cycle de poids négatif est accessible à partir de v et peut revenir à v. C'est plus fort que la simple recherche d'un bord négatif ; des arêtes négatives peuvent exister dans des graphiques avec des chemins les plus courts parfaitement valides.

Si l'enquêteur demande quelles paires sont affectées, identifiez chaque i et j pour lesquels je peux atteindre un tel sommet v et v peut atteindre j. Ces paires peuvent parcourir le cycle négatif de manière arbitraire plusieurs fois, de sorte que leur valeur de chemin le plus court n'est pas finie.

Quand devriez-vous choisir un autre algorithme du chemin le plus court ?

Utilisez la recherche en largeur pour les graphiques non pondérés, Dijkstra pour les problèmes à source unique avec des poids non négatifs et Bellman-Ford pour une source unique lorsque les poids négatifs ou la détection de cycle négatif accessible sont importants. Floyd – Warshall est le choix direct lorsque les distances toutes paires sont requises et que le temps cube est acceptable.

Quelles erreurs d’entretien éviter ?

Ne mettez pas k dans une autre boucle, n'oubliez pas les zéros sur la diagonale, n'ajoutez pas l'infini sans garde, ne confondez pas les arêtes négatives avec les cycles négatifs ou ne prétendez pas que l'espace matriciel O(V²) inclut automatiquement l'entrée dans chaque représentation. Précisez si le graphique est orienté, s'il existe des bords parallèles et si l'intervieweur a besoin de distances, de chemins ou de paires affectées par le cycle.

Pratiquez le workflow de l'assistant d'entretien de codage, comparez l'algorithme Bellman-Ford et consultez l'aide-mémoire sur la complexité Big O.

Questions fréquemment posées

Pratiquez l'invariant, pas seulement les boucles

YesToTheOffer peut vous aider à structurer une explication de codage, à l'ancrer dans vos notes de préparation privées, à examiner les cas extrêmes et à conserver la transcription de l'entretien pour une révision ultérieure.