traverse direct graph with multiplicative edges

Question

I have a graph like this one:

Each step from one node to another is a multiplication.

So for instance given the entry node TE and an entry value of 1.

TE = 1

TB = 1/10010

GB = 999/(10010*1000)

GE = (19990*999)/(10010*1000)

and so on.

I want to find the best path from TE to TE to return the highest value.

In this case is

TE TB GB GE TE = 1,993010988

I tried to apply Dijkstra's SPF but it doesn't work because each step can increment or decrement so it's not monotone

neither Bellman–Ford algorithm is applicable here because the graph contains negative cycle. (e.g. TE TB TE).

Anyone has some clue if this problem has a solution ?

Answer 1

The fact that the weights are multiplicative is essentially irrelevant – you can always take logs, add the logs, then exponentiate. However, looking for the shortest simple path (i.e., no repeated vertices, so you're not whizzing round negative cycles) is an NP-hard problem when there are negative-weight cycles, as explained by Danny Pflughoeft on CS Theory SE. Essentially, longest path in a graph where all weights are non-negative becomes shortest path if you negate all the edge weights, but Hamiltonian path reduces easily to longest path.

You're now allowed to complain that I'm a complexity theorist, since you asked for an algorithm and I said "There's no fast one" as if that was the complete answer.

Wait, now I'm allowed to complain. You tagged your question "shortest-path" but you're actually looking for longest paths. That's straight-up NP-hard. Just give every edge weight $2$ and the longest simple path has weight $2^n$ if, and only if, the graph has a Hamiltonian cycle.