10.4 The Real Bellman-Ford algorithm

Question 1

How can we cache the edges for Weighted Interval Scheduling (using a table)

Answer 1

• Start from k=0 and build corresponding path using best value on prev line

Question 2

How do we cache the values for weighted interval scheduling without using a table

Answer 2

• Can either 1) store prev line (all we use) or 2) just store current line (turns out it works better)
• Current line will mean that you can jump to better solution faster (ie maybe k is inconsistent) but not a problem
• All initialised to infinity (and store their edge)

Question 3

What is the final psuedocode for the Bellman-Ford algorithm (weighted interval scheduling)

Answer 3

• Start with k = 0, build up values. For each itteration check the best path from each vertex.
• At end traverse best path to output it

Question 4

What are some other pathfinding algorithms to be aware of

Answer 4