1

给定：具有加权边的有向无环图，其中一个节点可以有多个父节点。

问题：对于根节点的每个子节点，找到从该子节点到可以到达的某个叶子的最小成本（权重之和）路径。一个节点只能出现在一个这样的最小成本路径中。

示例图：

示例图

在上图中，对于节点 2，所有可用路径为：

2 -> 5  
2 -> 1 -> 9 -> 6
2 -> 1 -> 10 -> 6
Among which 2 -> 1 -> 10 -> 6 has minimum cost of 3.5

同样，对于节点 4，所有可用路径为：

4 -> 11 -> 8
4 -> 7 -> 10 -> 6 
Among which 4 -> 7 -> 10 -> 6 has minimum cost of 3.0

目前的结果是：

For node 2, the path is 2 -> 1 -> 10 -> 6 : Cost 3.5
For node 4, the path is 4 -> 7 -> 10 -> 6 : Cost 3.0
For node 3, there is no such path.

我写了一个代码来做到这一点。现在，如果这样的最小成本路径没有任何共同的节点，算法将停止并为我提供根节点的所有子节点的最小成本路径。

但是，如果存在一个共同的节点，我必须只在其中一个节点中保留它。原因是通常这种多父节点是由于噪声数据。一个节点应该只属于一个父节点。我试图将这样的节点保持在成本最低的路径中。所以在这里，节点 10 属于节点 4 的最小路径，其成本为 3.0，而节点 2 的最小路径的成本为 3.5。与节点 6 的逻辑相同。因此，我将只比较取消关联一些多父节点的成本。解除关联并不意味着边缘将被移除。我所做的就是为节点的数据结构中的每个节点保存最佳父节点。例如，节点 10 将有一个条目说“最佳父节点是节点 7”，节点 6 将有一个条目“最佳父节点是节点 10”。

因此，逻辑如下所示：

Do:
    For each child node of the root:
         Find out min-cost path. Store that path and the cost.
    If conflicting paths exist:
         Compare the costs of conflicting paths and save "best parent" for each node. 
While there were conflicting paths;

问题：

  1. 这个逻辑有意义吗？我担心这种消除冲突的迭代方式对于某些图表可能不会收敛。例如，在重新计算节点 2 的最小路径时，如果现在发现 2 -> 5 是最小路径，并假设在第一次迭代期间节点 5 正在其他节点的最小路径中使用，那么我将不得不将节点 5 的“最佳父级”重新分配为节点 2 并重新迭代。简而言之，每次我尝试修复某个节点的最小路径时，我可能会更改另一个节点的最小路径。这样的算法可以收敛到某个解决方案吗？如果是，它的复杂性是多少？

  2. 有没有办法在首先计算最小成本路径之前消除这种冲突？

4

1 回答 1

0

是动态规划。

首先将所有边反转以形成一个新图，我们称之为 newG。

  1. 在 newG 中，没有父节点的节点的值为 0。
  2. 对于 newG 中它有父节点的每个节点，计算它的父节点的值，然后选择最小值父节点，它必须是结果的一部分。
  3. 当从原点 gtaph 询问路径时，新 G 中的答案是相同的。（可能是答案中的边缘顺序相反）。

时间 O(n)

于 2014-08-04T10:05:30.527 回答