0
$\begingroup$

I have a graph like this one:Graph

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 ?

$\endgroup$
2
  • 1
    $\begingroup$ 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.) $\endgroup$
    – D.W.
    Nov 9, 2017 at 1:51
  • $\begingroup$ 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 ? $\endgroup$ Nov 9, 2017 at 8:10

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.