algorithm - 如何在有向无环图中找到 '5' 最重要的路径？

Question

我有一个有向无环图 (DAG)，每个节点都有一个权重。我想找到前“n”条(例如 5 条)最有权重的路径，其中路径的权重定义为其节点所有权重的总和。我怎样才能做到这一点？

准确性是可取的，但可以牺牲性能。该图可能有 10,000 多个节点和/或边。

编辑:权重将是大于或等于零的数字。

Answer 1

1. 对图进行拓扑排序。
2. 将每个图的节点与 n 元素优先级队列(最小堆)相关联。
3. 对于每个节点(按排序顺序)，从优先级队列中弹出路径权重，添加节点的权重，并将它们传递给每个后代。当一个节点从它的父节点接收到权重时，它应该将它插入到关联的优先级队列中。
4. 对于每个叶节点，从优先级队列中弹出路径权重，添加节点的权重，并将它们插入到一个公共(public)优先级队列中。在处理完最后一个节点后，此优先级队列包含“n”条最有权重的路径的权重。如果与权重一起存储反向指针，则可以恢复这些路径。