10.3 The Bellman-Ford Algorithm

Question 1

What does excluding negative cycles mean for the shortest walk in a graph (including negative weights)

Answer 1

• It is a path. Ie will not take any cycles since pos weight

Question 2

Why doesn’t Dijksta’s algorithm work for negative weights?

Answer 2

• Built on principle that the shortest path out of set is the best
• Not true for negative weights

Question 3

What is the dynamic programming idea for weighted interval scheduling (ie how to break up problem)

Answer 3

• Always think about choices with DP
• We choose which vertex to go to next (then take best path from there)
• Can recursively evaluate this

Question 4

What is the slow recursive algorithm for weighted interval scheduling

Answer 4

• Recurse on the graph without that node

Question 5

What is the trick for consolodating weighted interval scheduling calls (ie reframing the problem)

Answer 5

• Make it a walk with at most k edges (will thus be a path)

Question 6

What is the recursive psuedocode for the reframed weighted interval scheduling problem

Answer 6