具有多父节点的有向无环图

Question

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

问题：对于根节点的每个子节点，找到一条从该子节点到某个叶的最小代价（权重之和）路径。一个节点只能存在于一个这样的最小开销路径中。

图表示例：

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

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.

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;

>

这个逻辑有道理吗？我担心这种消除冲突的迭代方式可能对某些图不收敛。例如，在重新计算节点2的最小路径时，如果现在发现2->5是最小路径，并且假设在第一次迭代期间，节点5在其他节点的最小路径中使用，那么我必须将节点5的“最佳父”重新分配为节点2，并重新迭代。在坚果壳中，每次我试图修复某个节点的最小路径时，我可能会改变另一个节点的最小路径。这样的算法能收敛到某个解吗？如果是，它的复杂性会是多少？

在计算最小成本路径之前，有没有一种方法可以消除这种冲突？

Answer 1

是动态编程。

首先将所有边反向生成一个新的图，我们称之为NEWG。

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