Algorithm for finding the cost of a node based on previous nodes in a cyclic graph
I have a partially or fully circular graph for which I want to calculate the cost of each node based on the weighted sum of the costs of the previous nodes. Nodes with no incoming edges have a fixed cost assigned to them.
For example, the following graph has each node labeled with its calculated cost (the cost of node 2 is fixed) and each edge is labeled with the weight of the previous node. So the cost of node 1.33 is calculated from 1 * 0.33 + 0.5 * 2.
I am currently using an iterative approach to calculate the cost of each node to within some epsilon, but I am looking for an algorithm that can calculate the cost accurately. The above example is pretty simple, the actual problem is about ~ 100 nodes per highly connected component. Any suggestions for an algorithm that might solve this?
source to share
You can build a system of linear equations and solve them. In the example you gave, node 2 is fixed since it has no incoming edge. By assigning a value x
to the top right node, y
to the top left node and z
to the bottom node, you will create the following system of linear equations
x = 0.5*2 + 1*y
y = 0.5*z
z = 0.5*x
x=1.33333, y=0.333333, z=0.666667
source to share