Förberedelse inför kodningsintervjuer · Lektion

Bellman-Ford och negativa kanter

Hantera negativa vikter och upptäck cykler

Lektion 3 av 413 steg

Bellman-Ford och negativa kanter är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 3 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.

När Dijkstra misslyckas

Dijkstra litar på att ett avstånd som tas bort är slutgiltigt, men en negativ kant kan senare göra en väg billigare. Därför fungerar algoritmen inte i det fallet.

Bellman-Ford gör entré

Bellman-Ford hanterar negativa kantvikter. Algoritmen är långsammare än Dijkstra men robust när den giriga logiken inte går att lita på.

Den centrala operationen

Algoritmen relaxerar upprepade gånger varje kant: om dist[u] plus kantvikten är mindre än dist[v], uppdateras dist[v] till det mindre värdet.

if dist[u] + w < dist[v]:
    dist[v] = dist[u] + w

Hur många omgångar

En kortaste väg använder högst V-1 kanter, så V-1 omgångar där varje kant relaxeras räcker för att fastställa alla avstånd.

for _ in range(n - 1):
    relax_all_edges()

Initiera avstånden

Börja med att sätta varje avstånd till oändlighet, förutom startnoden som får avståndet noll, precis som i Dijkstra.

dist = [float('inf')] * n
dist[src] = 0

Ett helt varv

Varje varv går igenom hela kantlistan en gång och relaxerar varje kant. Förbättringar sprids ut en kant per varv.

for u, v, w in edges:
    if dist[u] + w < dist[v]:
        dist[v] = dist[u] + w

Varför V-1 räcker

Efter k varv är alla kortaste vägar med k kanter korrekta. Efter V-1 varv är varje enkel kortaste väg färdig.

Det extra varvet

Kör ytterligare ett varv. Om något avstånd fortfarande minskar fortsätter något att bli billigare, vilket visar att det finns en negativ cykel.

Upptäck negativa cykler

En negativ cykel innebär att ingen ändlig kortaste väg finns, eftersom Ni kan köra runt cykeln hur många gånger som helst och sänka kostnaden utan gräns.

for u, v, w in edges:
    if dist[u] + w < dist[v]:
        return 'negative cycle'

Körtiden

Ni relaxerar E kanter under V varv, så Bellman-Ford körs på O(V * E), vilket fungerar bra för små eller medelstora grafer.

Dijkstra eller Bellman-Ford

Välj Dijkstra för icke-negativa vikter och hög hastighet. Välj Bellman-Ford när negativa vikter förekommer eller när Ni måste upptäcka en negativ cykel.

Snabbkontroll

Efter V-1 varv minskar ett avstånd fortfarande under ytterligare ett varv. Vad innebär det?

Besvara frågan i den interaktiva lektionen

Sammanfattning: Bellman-Ford

Relaxera alla kanter under V-1 varv och kör sedan ett extra varv för att upptäcka negativa cykler. Algoritmen körs på O(V*E), men fungerar där Dijkstra inte gör det. ✅

Gratis att börja

Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis

Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.

Kurser: 90
Lektioner: 360

Börja lära dig gratis Visa hela kursen

Vanliga frågor

Är lektionen ”Bellman-Ford och negativa kanter” gratis?

Ja – hela texten till ”Bellman-Ford och negativa kanter” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.

Vad lär jag mig i ”Bellman-Ford och negativa kanter”?

Hantera negativa vikter och upptäck cykler Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.

Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?

Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 3 av 4.

Hur lång tid tar lektionen ”Bellman-Ford och negativa kanter”?

De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.

Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?

Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.

Alla lektioner i den här kursen

← Tillbaka till Förberedelse inför kodningsintervjuer