0Pricing
Coding Interview Prep · Lekcja

Bellman-Ford i cykle ujemne

Wykonywać n-1 przebiegów relaksacji po wszystkich krawędziach, wykrywać cykle ujemne w dodatkowym przebiegu oraz wyjaśniać, dlaczego Dijkstra nie działa dla krawędzi o ujemnych wagach

Bellman-Ford i cykle ujemne to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Dlaczego istnieje algorytm Bellmana-Forda

Algorytm Bellmana-Forda rozwiązuje problem najkrótszych ścieżek z jednego źródła, podobnie jak algorytm Dijkstry, ale obsługuje ujemne wagi krawędzi. Potrafi również wykrywać ujemne cykle — cykle, których łączna waga jest ujemna, przez co nie można określić skończonej wartości najkrótszej ścieżki przechodzącej przez taki cykl. Choć algorytm Bellmana-Forda jest wolniejszy od algorytmu Dijkstry, jest właściwym wyborem zawsze, gdy graf może zawierać krawędzie o ujemnych wagach.

Relaksacja: podstawowa operacja

Algorytm Bellmana-Forda opiera się na jednej operacji: relaksacji. Relaksacja krawędzi (u, v, w) oznacza: jeśli dist[u] + w < dist[v], należy zaktualizować dist[v] = dist[u] + w. Wielokrotnie relaksujemy wszystkie krawędzie. Najważniejszy wniosek jest następujący: każda najkrótsza ścieżka ma co najwyżej V-1 krawędzi (w grafie bez ujemnych cykli). Dlatego V-1 rund relaksacji obejmujących wszystkie krawędzie wystarczy do znalezienia wszystkich najkrótszych ścieżek.

Implementacja algorytmu Bellmana-Forda

Graf należy przedstawić jako listę krawędzi [(u, v, weight)]. Należy zainicjalizować dist[source] = 0, a wszystkim pozostałym wierzchołkom przypisać inf. Następnie należy wykonać V-1 rund, relaksując wszystkie krawędzie w każdej rundzie. Każda aktualizacja, która wystąpi jeszcze w V-tej rundzie, wskazuje na obecność ujemnego cyklu.

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]

Dlaczego V-1 przebiegów wystarcza

Najkrótsza ścieżka w grafie bez ujemnych cykli odwiedza każdy wierzchołek co najwyżej raz, więc ma co najwyżej V-1 krawędzi. Po rundzie 1 najkrótsze ścieżki z maksymalnie jedną krawędzią są optymalne. Po rundzie 2 optymalne są najkrótsze ścieżki z maksymalnie dwiema krawędziami. Po V-1 rundach znaleziono wszystkie najkrótsze ścieżki, które mają co najwyżej V-1 krawędzi. Jeśli w rundzie V nadal zostanie zaktualizowana jakaś odległość, graf zawiera ujemny cykl osiągalny ze źródła.

Wykrywanie ujemnych cykli

Po V-1 przebiegach należy wykonać jeden dodatkowy przebieg po wszystkich krawędziach. Jeśli dla dowolnej krawędzi (u, v, w) zachodzi dist[u] + w < dist[v], oznacza to istnienie ujemnego cyklu, a najkrótsza ścieżka do niektórych wierzchołków ma wartość -infinity. Zastosowania w świecie rzeczywistym obejmują wykrywanie możliwości arbitrażu walutowego (ujemnych cykli w grafach z wagami logarytmicznymi) oraz wykrywanie niespójności w systemach ograniczeń.

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

Porównanie algorytmów Dijkstry i Bellmana-Forda

Algorytm Dijkstry: O((V+E) log V), wymaga nieujemnych wag, podejście zachłanne. Algorytm Bellmana-Forda: O(V × E), obsługuje ujemne wagi i wykrywa ujemne cykle. W większości zadań rekrutacyjnych z nieujemnymi wagami preferowany jest algorytm Dijkstry. Gdy pojawiają się ujemne wagi (np. „znajdź najkrótszą ścieżkę z krawędziami o ujemnym koszcie” lub „wykryj arbitraż”), właściwym rozwiązaniem jest algorytm Bellmana-Forda. Dla grafów gęstych najgorszy przypadek O(V³) algorytmu Bellmana-Forda jest porównywalny z algorytmem Floyda-Warshalla.

Zastosowanie: najtańsze loty z algorytmem Bellmana-Forda

Problem Cheapest Flights Within K Stops (LeetCode 787) można rozwiązać za pomocą zmodyfikowanego algorytmu Bellmana-Forda: należy wykonać dokładnie k+1 przebiegów relaksacji (ponieważ k przesiadek oznacza k+1 krawędzi). Należy użyć kopii odległości z poprzedniego przebiegu, aby zagwarantować, że w pojedynczym przebiegu nie zostanie użytych więcej przejść, niż dozwolono — w przeciwnym razie jeden przebieg mógłby połączyć wiele przejść.

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: optymalizacja oparta na kolejce

Shortest Path Faster Algorithm (SPFA) to zoptymalizowany algorytm Bellmana-Forda, który ponownie relaksuje tylko krawędzie wychodzące z wierzchołków, których odległość właśnie zaktualizowano, korzystając z kolejki. Złożoność w przypadku średnim wynosi O(E), ale w najgorszym przypadku nadal jest równa O(V × E). Algorytm SPFA rzadko jest wymagany podczas rozmów rekrutacyjnych, ale można wspomnieć o nim jako o optymalizacji, gdy algorytm Bellmana-Forda działa zbyt wolno na grafach rzadkich. Python nie ma wbudowanej implementacji SPFA, ale można ją łatwo zaimplementować za pomocą collections.deque.

Wykrywanie arbitrażu walutowego

Klasyczne zastosowanie algorytmu Bellmana-Forda: mając kursy wymiany walut, należy wykryć, czy arbitraż jest możliwy (czy istnieje cykl, w którym po wymianie walut otrzymuje się więcej niż na początku). Należy przekształcić problem, biorąc ujemny logarytm kursów wymiany. Arbitraż = cykl o ujemnej łącznej wadze logarytmicznej = ujemny cykl wykrywalny przez algorytm Bellmana-Forda. W ten sposób rzeczywiste problemy finansowe można sprowadzić do standardowego algorytmu.

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

Optymalizacja wczesnego zakończenia

Jeśli podczas pełnego przebiegu po wszystkich krawędziach nie zostanie zaktualizowana żadna odległość, kolejne przebiegi również niczego nie zaktualizują — należy zakończyć działanie wcześniej. Ta optymalizacja zmniejsza złożoność w najlepszym przypadku do O(E), gdy graf jest już optymalny po kilku przebiegach. Na początku każdego przebiegu należy ustawić flagę updated = False; jeśli po zakończeniu przebiegu nadal ma wartość False, należy natychmiast przerwać działanie algorytmu.

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

Algorytm Bellmana-Forda w grafach z listami sąsiedztwa

Gdy graf jest podany jako lista sąsiedztwa, a nie lista krawędzi, należy najpierw przekształcić go w listę krawędzi albo traktować wszystkie wpisy list sąsiedztwa jako krawędzie. Dla V=1000 i E=5000, V-1=999 przebiegów, z których każdy skanuje 5000 krawędzi, daje 4,995,000 operacji — wynik zdecydowanie mieszczący się w limitach czasowych. Dla bardzo gęstych grafów (E ≈ V²) najgorszy przypadek O(V³) odpowiada złożoności algorytmu Floyda-Warshalla, więc wybór zależy od kontekstu.

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

Szybki sprawdzian

Sprawdź swoje zrozumienie zagadnień z kursu Data Structures & Algorithms — Coding Interview Prep przedstawionych w tej lekcji.

Podsumowanie lekcji

W tej lekcji poznali Państwo następujące informacje: algorytm Bellmana-Forda relaksuje wszystkie krawędzie V-1 razy, aby obsługiwać krawędzie o ujemnych wagach, V-ty przebieg relaksacji, w którym nadal znajdowane są ulepszenia, wskazuje na ujemny cykl, a złożoność algorytmu wynosi O(V × E) w porównaniu z O((V+E) log V) algorytmu Dijkstry. Następnie omówimy algorytm Floyda-Warshalla do znajdowania najkrótszych ścieżek między wszystkimi parami wierzchołków w ramach jednego obliczenia o złożoności O(V³).

Często zadawane pytania

Czy lekcja „Bellman-Ford i cykle ujemne” jest bezpłatna?

Tak — pełny tekst „Bellman-Ford i cykle ujemne” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Co nauczysz się w „Bellman-Ford i cykle ujemne”?

Wykonywać n-1 przebiegów relaksacji po wszystkich krawędziach, wykrywać cykle ujemne w dodatkowym przebiegu oraz wyjaśniać, dlaczego Dijkstra nie działa dla krawędzi o ujemnych wagach Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?

Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.

Ile czasu zajmuje lekcja „Bellman-Ford i cykle ujemne”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?

Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

  1. Algorytm Dijkstry z kolejką priorytetową
  2. Bellman-Ford i cykle ujemne
  3. Floyd-Warshall: najkrótsze ścieżki między wszystkimi parami wierzchołków
  4. Opóźnienie sieci i odtwarzanie ścieżki
← Powrót do Coding Interview Prep