如何找到线性时间内可从 DAG 中的节点访问的最小值

Question

我正在尝试遵循 http://seed.ucsd.edu/mediawiki/images/4/43/Sol3.pdf 中的3.25（a）

我知道您必须先对图进行拓扑排序。但我不明白他们是如何获得最低成本的[w]。如果有 2 条来自 u 的传出边，您如何使用此算法解释它们？

Answer 1

这本质上是动态编程。当有多个传出节点时，您可以在每个阶段选择最小值。当您最终到达起点时，这给出了最小值。举个例子并逐步完成它。