基于循环图中的先前节点查找节点成本的算法

Question

我有一个部分或完全循环的图,我想根据前面节点的成本的加权和来计算每个节点的成本.没有传入边缘的节点具有分配给它们的固定成本.

例如,下面的图表标记了每个节点的计算成本(节点2的成本是固定的),每个边缘都标有前一个节点的权重.因此,节点1.33成本从1*0.33 + 0.5*2计算.

我目前使用迭代方法计算每个节点在某个epsilon内的成本,但我正在寻找一种能够精确计算成本的算法.上面的例子非常简单,实际问题涉及每个强连接组件约100个节点.对算法有什么建议可以解决这个问题吗？

Answer 1

您可以构建一个线性方程组并解决它们.在您给出的示例中,节点2是固定的,因为它没有传入边缘.将值分配x给右上节点,y左上节点和z下节点,可构建以下线性方程组

x = 0.5*2 + 1*y
y = 0.5*z
z = 0.5*x

x=1.33333,   y=0.333333,   z=0.666667