I have weighted connected directed graph with cycles which can have multiple edges and loops (edge from vertex back to itself). Weight of each edge is its length (always positive integer). There always is a path from vertex $v_0$ to every other vertex (including itself).
I need to find greatest common divisor (GCD) of all cycles' (from $v_0$ to itself) lengths. It always exists and is a divisor of shortest cycle (from $v_0$ to itself) length. Note that concatenating any number of such cycles also gives valid cycle.
I know one way to find GCD. We can find generating function of number of cycles of certain length (using Gaussian elimination for example). Such generating function is always a rational function (ratio of polynomials). Then GCD of $x$ powers from denominator is actually GCD of all cycle lengths. However this is really computationally inefficient. Finding generating function always requires near cubic rational function arithmetic operations (cubic for Gaussian elimination but can be less if use sophisticated matrix multiplication, but that is not practical). However those arithmetic operations are exponential in time because coefficients grow exponentially (at least). There is possibility to simplify graph a bit by contracting vertices without loops and merge multiple loops on vertices, but that does not help much.
I am wondering if there is more efficient algorithm to solve this problem. Maybe there are papers on similar subject, however I did not find any.
Here you can see example of such graph. It has GCD=10.