Pseudokod

Lekcja 4 z 9 w kursie Algorytm Bellmana-Forda — algorytmy grafowe w Coddy.

bellmanFord(n, edges, source):
   dist = [INF, INF, ...]; dist[source] = 0
   repeat (n - 1) times:
      for each edge (u -> v, weight w):
         if dist[u] != INF and dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
   replace every remaining INF with -1
   return dist

// negative cycle: after n-1 passes, if any edge STILL relaxes, a
// negative cycle exists.

Warunek dist[u] != INF zapobiega tworzeniu ścieżek wychodzących z nieosiągalnych wierzchołków.
Przejście przez całą listę krawędzi to jeden przebieg. Bellman-Ford to po prostu powtarzanie tego przebiegu n - 1 razy.

Spróbuj swoich sił

Ta lekcja nie zawiera wyzwania z kodem.