Bellman Ford-algoritme: interviewgids voor coderen

TL; DR: Het Bellman Ford-algoritme vindt de kortste paden van één bron in een gewogen gerichte grafiek, zelfs als sommige randen een negatief gewicht hebben. Initialiseer de bronafstand op nul, alle andere op oneindig, versoepel elke rand tot V min 1 keer en voer vervolgens één extra passage uit: elke verdere verbetering bewijst dat er een haalbare cyclus met negatief gewicht bestaat.

Wat is het Bellman Ford-algoritme?

Bellman Ford is een kortste-pad-algoritme in dynamische programmeerstijl. Na de eerste volledige passage gebruiken de bekendste paden maximaal één rand; na de tweede maximaal twee randen. Een eenvoudig pad bevat maximaal V min 1 randen, wat zowel het aantal lussen als het juistheidsargument verklaart. In tegenstelling tot het algoritme van Dijkstra gaat Bellman Ford niet uit van niet-negatieve randgewichten.

Hoe verklaar je randontspanning?

Voor een lijn van u naar v met gewicht w vraagt ​​de relaxatie zich af of afstand[u] + w kleiner is dan afstand[v]. Voer de optelling alleen uit als u bereikbaar bent. Als de kandidaat beter is, update dan afstand[v] en stel voorganger[v] in op u. De voorgaande array is optioneel voor afstanden, maar u kunt hiermee het daadwerkelijke pad reconstrueren en uw resultaat duidelijk uitleggen.

Hoe traceer je Bellman Ford in een interview?

Gebruik een kleine grafiek en schrijf één afstandsrij per doorgang. Begin met bron A op 0 en elk ander hoekpunt op oneindig. Scan de volledige randlijst in een consistente volgorde en registreer elke update. Stop vroeg als een hele pas geen wijzigingen aanbrengt. Wees expliciet dat de randvolgorde tussenliggende rijen kan veranderen, maar niet de uiteindelijke correcte afstanden als er geen bereikbare negatieve cyclus bestaat.

Welke pseudocode moet je schrijven?

Creëer afstands- en voorgangerarrays en herhaal vervolgens een volledige randscan V minus 1 keer. Gebruik een gewijzigde vlag voor vroegtijdige beëindiging. Scan ten slotte nog een keer alle randen en rapporteer een negatieve cyclus als de bereikbare afstand nog kan verbeteren. Kies in de productiecode een numeriek type dat padsommen kan bevatten en de oneindigheidswacht bewaakt vóór toevoeging.

Wat zijn de complexiteiten in tijd en ruimte?

De standaardimplementatie van de aangrenzende randlijst wordt uitgevoerd in O(VE)-tijd omdat deze E-randen kan scannen bij elk van V minus 1 doorgangen, plus één detectiedoorgang. Het gebruikt O(V)-hulpruimte voor afstanden en voorgangers. Vroegtijdig stoppen verbetert gunstige inputs, maar de worstcasegrens blijft O(VE).

Wanneer kies je voor Bellman Ford in plaats van Dijkstra?

Kies Bellman Ford wanneer negatieve randgewichten zijn toegestaan ​​of wanneer de interviewer expliciet vraagt ​​om bereikbare detectie van negatieve cyclussen. Kies Dijkstra met een prioriteitswachtrij voor grafieken waarvan de randgewichten allemaal niet-negatief zijn, omdat deze normaal gesproken sneller zijn. Voor de kortste paden van alle paren moet u eerst de grafiekdichtheid, de negatieve gewichten verduidelijken en aangeven of paden of alleen afstanden vereist zijn.

Welke fouten moet je vermijden?

Ontspan niet vanuit een onbereikbaar hoekpunt, verwar een negatieve rand niet met een negatieve cyclus, of claim dat elke negatieve cyclus het resultaat ongeldig maakt: alleen een cyclus die bereikbaar is vanaf de bron heeft invloed op de kortste paden. Vermijd ook om alleen V min 2 passages uit te voeren, de laatste detectiepassage over te slaan of een pad te reconstrueren zonder voorgangers te behouden.

Hoe kun je de uitleg oefenen?

Oefen drie versies: een definitie van 30 seconden, een uitleg van de juistheid van twee minuten en een volledige implementatie. Test een onbereikbaar hoekpunt, één negatieve rand zonder cyclus, een bereikbare negatieve cyclus en een grafiek die vroeg stabiliseert. Dit scheidt de opgeslagen code van echt begrip.

Gebruik AI om materiaal dat u al begrijpt te ordenen, uitleg te oefenen en uw prestaties te beoordelen. Volg de regels van de werkgever en de assessmentaanbieder en verzin nooit ervaringen, cijfers of resultaten.

Ga verder met de AI-interview copilot-gids, cv-gegronde voorbereiding en workflow voor beoordeling na het interview.

Veelgestelde vragen

Oefen met bewijs, niet met een script

YesToTheOffer kan de voorbereiding en de realtime antwoordstructuur verwerken in uw cv, rolbeschrijving en privénotities, en vervolgens een transcript bewaren voor beoordeling na het interview.