algorithm - 如何在路径列表中找到唯一最短路径列表？

Question

想象一下，我有一个如下所示的树形图，其中一个节点可以有多个子节点，依此类推......（一个节点只能有一个父节点）。如果我有一个沿该图的路径列表，我如何找到这些路径中唯一且最短的子集？

示例输入（路径列表）：

[1, 2, 3]
[1, 2]
[1, 7]
[1, 8, 9, 10]

预期输出：

[1, 2]
[1, 7]
[1, 8, 9, 10]

路径被忽略，[1, 2, 3]因为它比 长[1, 2]，而[1, 8, 9, 10]路径被保留，因为它是唯一的。

标签： algorithmtreegraph-theoryshortest-path

Answer 1

首先，按长度对输入路径进行排序。维护一组叶节点。这将包含每个有效路径的最后一个节点。添加叶节点后，我们将禁止任何包含该叶节点的路径。添加路径时，请根据叶节点集检查其每个成员。如果您得到匹配，则路径无效，否则它是有效的，您应该将它的最终元素添加到叶节点集。

这是列表数量的 O(n log n) 和所有列表中元素数量的线性关系。