algorithm - DAG中所有路径的边积之和

Question

我有一个带加权边的有向无环图。我的目标是找到“第一个”和“最后一个”级别之间所有路径中的边乘积之和。例如，在这种情况下，这将是 2*3 + 2*1 + 4*2 + 4*4 + 3*3 + 3*1 + 2*2 + 2*4 = 56。在实际图表中，我有20-30 级。有什么有效的方法可以做到这一点吗？

Answer 1

你可以使用一个简单的DFS来解决这个问题:

    Node s; // starting node
    Integer result = 0
    Function sumProduct(Node currentNode){
            mark currentNode as visited
            for each connected node to currentNode which is not visited do

                 result += edgeCost(currentNode to neighbor) + sumProduct(Neighbor);
            end for

                 return result
    }

// call function with the starting node: 

sumProduct(s);