DSA Interview Prep · Lektion

Bellman-Ford og negative cykler

Q: Er lektionen “Bellman-Ford og negative cykler” gratis?

Ja — alle 3 lektioner i læringssporet DSA Interview Prep, inklusive “Bellman-Ford og negative cykler”, kan læses gratis i deres fulde længde her på webstedet. Derefter låser CoddyKit PRO alle lektioner op samt interaktive øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. DSA Interview Prep-kurset indeholder 4 lektioner i alt.

Q: Skal jeg have erfaring for at begynde på DSA Interview Prep?

Der kræves ingen tidligere erfaring. DSA Interview Prep på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 2 af 4.

Q: Hvor lang tid tager lektionen “Bellman-Ford og negative cykler”?

De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.

Q: Kan jeg skrive og køre kode i denne DSA Interview Prep-lektion?

Ja. Alle DSA Interview Prep-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.

Kør n-1 afslapningsgennemløb over alle kanter, registrér negative cykler med et sidste gennemløb, og forklar, hvorfor Dijkstra fejler på kanter med negative vægte.

Lektion 2 af 413 trin

Bellman-Ford og negative cykler er en gratis DSA Interview Prep-lektion på CoddyKit. Dette er lektion 2 af 4. Du kan læse alle 3 lektioner i dette læringsspor gratis i deres fulde længde — derefter låser CoddyKit PRO alle lektioner op samt praktiske øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Den er en del af læringsforløbet i DSA Interview Prep, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. DSA Interview Prep-kurset indeholder 4 lektioner i alt.

Hvorfor Bellman-Ford findes

Bellman-Ford løser problemet med korteste sti fra én kilde ligesom Dijkstra, men håndterer negative kantvægte. Den registrerer også negative cyklusser — cyklusser, hvis samlede vægt er negativ, hvilket gør det umuligt at definere en endelig korteste sti gennem dem. Selvom Bellman-Ford er langsommere end Dijkstra, er den det korrekte valg, når grafen kan indeholde kanter med negative vægte.

Relaksation: Den grundlæggende operation

Bellman-Ford er bygget på én operation: relaksation. At relaksere kanten (u, v, w) betyder: Hvis dist[u] + w < dist[v], skal du opdatere dist[v] = dist[u] + w. Vi relakserer gentagne gange alle kanter. Den afgørende indsigt er: Enhver korteste sti har højst V-1 kanter (i en graf uden negative cyklusser). Derfor er V-1 runder, hvor alle kanter relakseres, tilstrækkelige til at finde alle korteste stier.

Implementering af Bellman-Ford

Repræsenter grafen som en kantliste [(u, v, weight)]. Initialisér dist[source] = 0 og alle andre værdier til inf. Kør V-1 runder, hvor alle kanter relakseres i hver runde. En opdatering, der stadig sker i den V. runde, angiver en negativ cyklus.

def bellman_ford(V, edges, source):
    dist = [float('inf')] * V
    dist[source] = 0
    
    # V-1 relaxation passes
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    
    # V-th pass: detect negative cycle
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return None  # negative cycle exists
    
    return dist

edges = [(0,1,4),(0,2,5),(1,2,-3),(2,3,1)]
print(bellman_ford(4, edges, 0))  # [0, 4, 1, 2]

Hvorfor V-1 gennemløb er tilstrækkelige

En korteste sti i en graf uden negative cyklusser besøger hver node højst én gang, så den har højst V-1 kanter. Efter runde 1 er de korteste stier med én kant optimale. Efter runde 2 er de korteste stier med to kanter optimale. Efter V-1 runder er alle korteste stier, som bruger højst V-1 kanter, fundet. Hvis runde V stadig opdaterer en afstand, indeholder grafen en negativ cyklus, der kan nås fra kilden.

Registrering af negative cyklusser

Efter V-1 gennemløb skal du køre ét ekstra gennemløb over alle kanter. Hvis en kant (u, v, w) opfylder dist[u] + w < dist[v], findes der en negativ cyklus, og den korteste sti til nogle noder er -infinity. Anvendelser fra virkeligheden omfatter registrering af arbitragemuligheder ved valutaveksling (negative cyklusser i grafer med logaritmiske vægte) og registrering af uoverensstemmelser i begrænsningssystemer.

def has_negative_cycle(V, edges, source):
    dist = [float('inf')] * V
    dist[source] = 0
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    # Nth pass
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return True  # negative cycle detected
    return False

# Negative cycle: 1->2->3->1 with weights -1,-1,1 (sum=-1)
edges_neg = [(0,1,1),(1,2,-1),(2,3,-1),(3,1,1)]
print(has_negative_cycle(4, edges_neg, 0))  # True

Sammenligning af Dijkstra og Bellman-Ford

Dijkstra: O((V+E) log V), kræver ikke-negative vægte, grådig tilgang. Bellman-Ford: O(V × E), håndterer negative vægte og registrerer negative cyklusser. Til de fleste opgaver ved tekniske jobsamtaler med ikke-negative vægte foretrækkes Dijkstra. Når der forekommer negative vægte (for eksempel 'find den korteste sti med kanter med negativ pris' eller 'registrér arbitrage'), er Bellman-Ford svaret. For tætte grafer kan Bellman-Fords værste tilfælde på O(V³) sammenlignes med Floyd-Warshall.

Anvendelse: Billigste flyrejser med Bellman-Ford

Cheapest Flights Within K Stops (LeetCode 787) kan løses med en modificeret Bellman-Ford: Kør præcis k+1 relaksationsrunder (fordi k stop betyder k+1 kanter). Brug en kopi af afstandene fra den forrige runde for at sikre, at vi ikke bruger flere hop end tilladt i én runde — ellers kunne en enkelt runde kæde flere hop sammen.

def findCheapestPrice_bf(n, flights, src, dst, k):
    dist = [float('inf')] * n
    dist[src] = 0
    
    for _ in range(k + 1):  # k stops = k+1 edges
        temp = dist[:]  # copy to avoid using updated dist in same pass
        for u, v, w in flights:
            if dist[u] != float('inf') and dist[u] + w < temp[v]:
                temp[v] = dist[u] + w
        dist = temp
    
    return dist[dst] if dist[dst] != float('inf') else -1

print(findCheapestPrice_bf(4,[[0,1,100],[1,2,100],[0,2,500]],0,2,1))  # 200

SPFA: Købaseret optimering

Shortest Path Faster Algorithm (SPFA) er en optimeret version af Bellman-Ford, som kun relakserer kanter fra noder, hvis afstand netop blev opdateret, ved hjælp af en kø. Gennemsnitstilfældet er O(E), men værste tilfælde er stadig O(V × E). SPFA er sjældent nødvendig ved tekniske jobsamtaler, men du kan nævne den som en optimering, når Bellman-Ford er for langsom på sparsomme grafer. Python har ikke en indbygget SPFA, men den er ligetil at implementere med collections.deque.

Registrering af valutaarbitrage

En klassisk anvendelse af Bellman-Ford: Givet valutakurser skal du registrere, om arbitrage er mulig (en cyklus, hvor valutakonvertering giver mere tilbage, end du startede med). Transformér ved at tage den negative logaritme af valutakurserne. Arbitrage = en cyklus med negativ samlet logaritmisk vægt = en negativ cyklus, som Bellman-Ford kan registrere. På den måde omsættes finansielle problemer fra virkeligheden til standardalgoritmen.

import math

def has_arbitrage(rates):
    n = len(rates)
    # Transform: -log(rate) converts product to sum
    log_rates = [[-math.log(rates[i][j]) for j in range(n)] for i in range(n)]
    edges = [(i,j,log_rates[i][j]) for i in range(n) for j in range(n) if i != j]
    
    dist = [float('inf')] * n
    dist[0] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return True  # arbitrage!
    return False

Optimering med tidlig afslutning

Hvis ingen afstand opdateres i en hel gennemgang af alle kanter, vil efterfølgende gennemgange heller ikke opdatere noget — afslut tidligt. Denne optimering reducerer kompleksiteten i bedste fald til O(E), når grafen allerede er optimal efter få gennemgange. Tilføj en markør updated = False i begyndelsen af hver gennemgang; hvis den stadig er False efter gennemgangen, skal du straks afbryde.

def bellman_ford_optimised(V, edges, source):
    dist = [float('inf')] * V
    dist[source] = 0
    for _ in range(V - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break  # no more improvements possible
    return dist

Bellman-Ford på grafer med nabolister

Når grafen er givet som en naboliste i stedet for en kantliste, skal du først konvertere den til en kantliste eller gennemløbe alle poster i nabolisten som kanter. For V=1000 og E=5000 giver V-1=999 gennemløb, hvor 5000 kanter scannes i hvert, 4.995.000 operationer — det er langt inden for tidsgrænserne. For meget tætte grafer (E ≈ V²) svarer værste tilfælde på O(V³) til Floyd-Warshall, så valget afhænger af konteksten.

from collections import defaultdict

def bellman_ford_adj(V, adj, source):
    # Convert adjacency list to edge list
    edges = [(u, v, w) for u in range(V) for v, w in adj[u]]
    dist = [float('inf')] * V
    dist[source] = 0
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist

Hurtigt tjek

Afprøv din forståelse af begreberne i Data Structures & Algorithms — Coding Interview Prep fra denne lektion.

Besvar den i den interaktive lektion

Opsummering af lektionen

I denne lektion har du lært: Bellman-Ford relakserer alle kanter V-1 gange for at håndtere kanter med negative vægte, et V. relaksationsgennemløb, der stadig finder forbedringer, angiver en negativ cyklus, og algoritmen er O(V × E) sammenlignet med Dijkstras O((V+E) log V). Næste emne er Floyd-Warshall til korteste stier mellem alle nodepar i en enkelt beregning på O(V³).

Gratis at komme i gang

Lær Python med en AI-underviser — gratis

Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.

Kurser: 30
Lektioner: 120

Start gratis Se hele kurset

Ofte stillede spørgsmål

Er lektionen “Bellman-Ford og negative cykler” gratis?