# traverse direct graph with multiplicative edges

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 ?

• What's the context in which you encountered this problem? Can you cite your sources? Also, what if there's a cycle that, each time you traverse it, increases the current value? Do you want a simple path (doesn't contain a cycle) or the best path even if it contains a cycle? (Related: en.wikipedia.org/wiki/Longest_path_problem.)
– D.W.
Nov 9, 2017 at 1:51
• yes simple path is enogh as lon as it returns to TE (is it still a simple graph if first and last are the same ? - which is my last point about Bellman-Ford) if start and end are the same is it still Bellman-Ford computable ? Nov 9, 2017 at 8:10

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.