小编Yan*_* Li的帖子

给定有向图,将权重分配给每个节点.
从任何节点A开始,将有一组可以从A到达的节点.
将SUM定义为该集合的总权重.

问题:如何有效地计算此图中每个节点的SUM？
该图可能包含数百万个节点.

更新1:
图形数据结构由一组起始节点组成,每个节点都有一组指向节点.

我尝试过:
递归计算每个节点的后代,并根据后代集计算SUM.这种递归效率非常低,因为我必须多次设置union,uteration操作.此外,我试图在每个节点缓存后代集.但是,它很容易耗尽内存.
那么,还有其他解决方案吗？

更新2:
示例图,边缘全部是定向的,上部节点指向较低的节点

结果应为
SUM(1)= 55 SUM(2)= 35 SUM(3)= 41 SUM(4)= 19 SUM(5)= 22 SUM(6)= 25 ......