CodeBlanks Logo Icon CodeBlanks
Login Register

Summary - Bellman-Ford

Run Bellman-Ford and print distances in a mini task.

Summary - Bellman-Ford

In this group you learned Bellman-Ford, which supports negative weights. Edge list, edge loop and negative cycle check combine into the solution.

Now you will write a check function that brings all pieces together. This summary unites the group's concepts in a single piece of code.

Practice has_negative_cycle function

Write has_negative_cycle(edges, n, src). Run Bellman-Ford, do one extra pass and return True if any edge still relaxes. Print True with print(has_negative_cycle([(0, 1, 1), (1, 2, -1), (2, 0, -1)], 3, 0)).

Starter code

solution.py
def has_negative_cycle(edges, n, src):
    # Check if a negative cycle exists

Sample solution

solution.py
def has_negative_cycle(edges, n, src):
    # Check if a negative cycle exists
    dist = [float('inf')] * n
    dist[src] = 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
    return False
print(has_negative_cycle([(0, 1, 1), (1, 2, -1), (2, 0, -1)], 3, 0))

Expected output

True

Questions and answers

Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.

1 When is Bellman-Ford's output valid?

  • No negative edges
  • Graph undirected
  • All edges positive
  • No negative cycle Correct answer

Explanation: The output is valid if no negative cycle exists.

2 Negative cycle condition

Question 
if dist[u] + w ____ dist[v]: return True
Answer 
if dist[u] + w < dist[v]: return True

Explanation: < is right.

3 Summary - Bellman-Ford: match the terms

Term Meaning
init_edges Edges
relax Relaxation
bellman_ford Algorithm
n-1 Passes

All lessons in Advanced

1 DP - Memoization

  1. What is memoization?
  2. Fibonacci memoization
  3. Dict-based cache
  4. Summary - Memoization

2 DP - Tabulation

  1. What is tabulation?
  2. Building the table
  3. Fibonacci tabulation
  4. Summary - Tabulation

3 LCS

  1. LCS definition
  2. DP table
  3. Backtracking the table
  4. Summary - LCS

4 Knapsack

  1. Knapsack problem
  2. 0/1 knapsack DP
  3. Decision table
  4. Summary - Knapsack

5 DP project

  1. Project: Overview
  2. Cost table
  3. DP solution
  4. Print the result

6 Matrix chain

  1. Multiplication order
  2. DP table
  3. Split point
  4. Summary - Matrix chain

7 Floyd-Warshall

  1. All pairs
  2. Triple loop
  3. Table update
  4. Summary - Floyd-Warshall

8 Dijkstra

  1. Single source
  2. Priority queue
  3. Relaxation
  4. Summary - Dijkstra

9 Bellman-Ford

  1. Negative weights
  2. Edge relaxation loop
  3. Negative cycle
  4. Summary - Bellman-Ford

10 Kruskal

  1. Minimum spanning tree
  2. Edge sorting
  3. Cycle check
  4. Summary - Kruskal

11 Prim

  1. Prim idea
  2. Priority queue
  3. Visited set
  4. Summary - Prim

12 Topological sort

  1. Dependency order
  2. DFS-based sort
  3. Kahn algorithm
  4. Summary - Topological sort

13 Union-find, trie, segment tree

  1. Union-find
  2. Trie
  3. Segment tree
  4. Summary - Advanced structures

14 Advanced final

  1. Challenge 1
  2. Challenge 2
  3. Challenge 3
  4. Challenge 4