Algorithme Bellman Ford : guide d'entretien de codage

TL;DR: L'algorithme de Bellman Ford trouve les chemins les plus courts à source unique dans un graphe orienté pondéré, même lorsque certaines arêtes ont des poids négatifs. Initialisez la distance source à zéro, toutes les autres à l'infini, relâchez chaque arête jusqu'à V moins 1 fois, puis effectuez une passe supplémentaire : toute amélioration supplémentaire prouve qu'un cycle de poids négatif atteignable existe.

Qu'est-ce que l'algorithme de Bellman Ford ?

Bellman Ford est un algorithme de chemin le plus court de style programmation dynamique. Après le premier passage complet, les chemins les plus connus utilisent au plus une arête ; après la seconde, au plus deux arêtes. Un chemin simple contient au plus V moins 1 arêtes, ce qui explique à la fois le nombre de boucles et l'argument d'exactitude. Contrairement à l'algorithme de Dijkstra, Bellman Ford ne suppose pas de poids de bord non négatifs.

Comment expliquez-vous la relaxation des bords ?

Pour une arête de u à v de poids w, la relaxation demande si la distance[u] + w est plus petite que la distance[v]. N'effectuez l'ajout que lorsque vous êtes joignable. Si le candidat est meilleur, mettez à jour la distance[v] et définissez le prédécesseur[v] sur u. Le tableau précédent est facultatif pour les distances, mais il vous permet de reconstruire le chemin réel et d'expliquer clairement votre résultat.

Comment retrouvez-vous Bellman Ford dans une interview ?

Utilisez un petit graphique et écrivez une ligne de distance par passe. Commencez par la source A à 0 et tous les autres sommets à l'infini. Parcourez la liste complète des bords dans un ordre cohérent, en enregistrant chaque mise à jour. Arrêtez-vous tôt lorsqu'un passage complet n'apporte aucun changement. Soyez explicite sur le fait que l'ordre des bords peut modifier les lignes intermédiaires mais pas les distances finales correctes lorsqu'il n'existe aucun cycle négatif accessible.

Quel pseudocode devez-vous écrire ?

Créez des tableaux de distance et de prédécesseur, puis répétez une analyse de bord complète V moins 1 fois. Utilisez un indicateur modifié pour une résiliation anticipée. Enfin, scannez à nouveau tous les bords et signalez un cycle négatif si une distance accessible peut encore s'améliorer. Dans le code de production, choisissez un type numérique capable de contenir les sommes de chemin et de garder la sentinelle infinie avant l'ajout.

Quelles sont les complexités temporelles et spatiales ?

L'implémentation standard de liste de bords de contiguïté s'exécute en temps O(VE) car elle peut analyser les bords E sur chacune des passes V moins 1, plus une passe de détection. Il utilise l'espace auxiliaire O(V) pour les distances et les prédécesseurs. L'arrêt précoce améliore les entrées favorables, mais la limite dans le pire des cas reste O(VE).

Quand devriez-vous choisir Bellman Ford au lieu de Dijkstra ?

Choisissez Bellman Ford lorsque les poids de bord négatifs sont autorisés ou lorsque l'intervieweur demande explicitement une détection de cycle négatif accessible. Choisissez Dijkstra avec une file d'attente prioritaire pour les graphiques dont les poids de bord sont tous non négatifs car il est normalement plus rapide. Pour les chemins les plus courts de toutes les paires, clarifiez d’abord la densité du graphique, les poids négatifs et si des chemins ou uniquement des distances sont requis.

Quelles erreurs faut-il éviter ?

Ne vous relâchez pas d'un sommet inaccessible, ne confondez pas une arête négative avec un cycle négatif, ou ne prétendez pas que tout cycle négatif invalide le résultat : seul un cycle accessible depuis la source affecte ses chemins les plus courts. Évitez également d'exécuter uniquement V moins 2 passes, de sauter la passe de détection finale ou de reconstruire un chemin sans conserver les prédécesseurs.

Comment pouvez-vous pratiquer l’explication ?

Pratiquez trois versions : une définition de 30 secondes, une explication de l'exactitude de deux minutes et une mise en œuvre complète. Testez un sommet inaccessible, une arête négative sans cycle, un cycle négatif accessible et un graphique qui se stabilise tôt. Cela sépare le code mémorisé de la véritable compréhension.

Utilisez l'IA pour organiser le matériel que vous comprenez déjà, répéter les explications et revoir vos performances. Suivez les règles de l'employeur et du prestataire d'évaluation et n'inventez jamais d'expériences, de chiffres ou de résultats.

Continuez avec le Guide du copilote d'entretien AI, la préparation fondée sur le CV et le flux de travail de révision post-entretien.

Questions fréquemment posées

Entraînez-vous avec des preuves, pas un script

YesToTheOffer peut ancrer la préparation et la structure de réponse en temps réel dans votre CV, la description de votre rôle et vos notes privées, puis conserver une transcription pour l'examen post-entretien.