如何在线性时间内找到从 DAG 中的节点可到达的最小值？
How do you find the smallest value reachable from a node in a DAG in linear time?
我正在尝试遵循 http://seed.ucsd.edu/mediawiki/images/4/43/Sol3.pdf
中的 3.25(a)
我知道您必须先对图进行拓扑排序。但我不明白他们如何获得成本 [w] 的最小值。如果你有 2 个出边，你如何使用这个算法来计算它们？
这本质上是动态规划。当有多个传出节点时，您可以在每个阶段选择最小值。当您最终到达起点时，这会给出总体最小值。画个例子，一步步过。
我正在尝试遵循 http://seed.ucsd.edu/mediawiki/images/4/43/Sol3.pdf
中的 3.25(a)我知道您必须先对图进行拓扑排序。但我不明白他们如何获得成本 [w] 的最小值。如果你有 2 个出边，你如何使用这个算法来计算它们？
这本质上是动态规划。当有多个传出节点时，您可以在每个阶段选择最小值。当您最终到达起点时，这会给出总体最小值。画个例子，一步步过。