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

Question

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

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

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

Answer 1

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