Prize Collecting

Given a directed graph, find the maximum amount of "prize" (weight of edges) possible to be obtained.

Dynamic Programming Solution

Dynamic Programming

1. Check for infinite cycle (positive cycle)
2. Negate edges and run Bellman-Ford
   • Bellman-Ford finds negative weight cycles.

Optimal Substructure

The solution for affects the solution for .

Subproblems

as the maximum prize collected starting at taking exactly steps.

If are nodes connected to , the subproblem can be seen as: