Сумма произведений краев всех путей в DAG

Question

У меня есть ориентированный ациклический граф с взвешенными краями. Моя цель - найти сумму произведений ребер во всех путях между «первым» и «последним» уровнями. Например, в этом случае это будет 2 * 3 + 2 * 1 + 4 * 2 + 4 * 4 + 3 * 3 + 3 * 1 + 2 * 2 + 2 * 4 = 56. На реальном графе у меня есть 20-30 уровней. Есть ли эффективный способ сделать это?

Answer 1

Попробуйте динамического программирования - начиная с последнего уровня и идти в обратном направлении. Для каждого узла v вычислите сумму S [v] для путей от этого узла до последнего уровня.

Для последнего уровня этот S [v] = 0 для всех v. Если у вас есть S [v] для всех узлов уровня i + 1, то вы вычисляете для всех узлов уровня i: S [u] = sum {v, st (u, v) является весом ребра (u, v) * S [v].

Answer 2

Вы можете использовать простой 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);