CodeBlanks Logo Icon CodeBlanks
Login Register

Negative weights

Bellman-Ford handles negative weights.

Negative weights

Bellman-Ford is a single-source shortest path algorithm that supports negative edge weights. It does what Dijkstra cannot.

The algorithm relaxes all edges n-1 times. This relies on the fact that the longest path has at most n-1 edges.

Edge list

Bellman-Ford works with an edge list rather than a graph object. Each edge is a (u, v, w) triple: from u to v with weight w.

This representation lets the algorithm traverse all edges one by one. Complexity is O(n·m); m is the edge count.

Practice init_edges function

Write init_edges(). Return the edge list. Print it with print(init_edges()).

Starter code

solution.py
def init_edges():
    # Return edge list

Sample solution

solution.py
def init_edges():
    # Return edge list
    return [(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5)]
print(init_edges())

Expected output

[(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5)]

Questions and answers

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

1 What is Bellman-Ford's advantage over Dijkstra?

  • Supports negative weights Correct answer
  • Uses less memory
  • Runs faster
  • Solves all pairs

Explanation: Bellman-Ford supports negative weights.

2 Edge definition

Question 
edges = [(0, 1, ____)]
Answer 
edges = [(0, 1, 4)]

Explanation: 4 is right.

3 Negative weights: match the terms

Term Meaning
(0,1,4) 0→1
(0,2,1) 0→2
(2,1,2) 2→1
(1,3,1) 1→3

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