DAG
Direct acyclic graph
Any such graph can be topological sorted(linearization)
DAG SPT Algorithm
(Only pick bold arrows)
Traverse in sequence, relax weight and pick a smaller one when reach a node.
Definition
Longest Increasing Subsequence
(Actually, we can do DAG SPT, reverse the concept of relaxation)
But twist the problem to fit algorithm is a better choice than changing algorithm.
That is Reduction.
Improvement: Without Graph
We can use results for small Q to compute results for large Q.
Implementation
Get rid of graph:
Just compare L and K instead of considering whether there’s an edge.