How to calculate the state of a graph?

Posted by zcb on Stack Overflow See other posts from Stack Overflow or by zcb
Published on 2012-10-14T03:05:20Z Indexed on 2012/10/14 3:37 UTC
Read the original article Hit count: 147

Filed under:
|
|
|
|

Given a graph G=(V,E), each node i is associated with 'Ci' number of objects. At each step, for every node i, the Ci objects will be taken away by the neighbors of i equally. After K steps, output the number of objects of the top five nodes which has the most objects.

Some Constrains: |V|<10^5, |E|<2*10^5, K<10^7, Ci<1000

My current idea is: represent the transformation in each step with a matrix. This problem is converted to the calculation of the power of matrix. But this solution is much too slow considering |V| can be 10^5.

Is there any faster way to do it?

© Stack Overflow or respective owner

Related posts about algorithm

Related posts about math