CODEWITHSUNDEEP
algorithmgraph-algorithmdijkstra
idkidkmaybemaybe
idkidkmaybemaybe

Reputation: 1

What would be the best way to solve this maximum path graph problem, is Dijkstra possible even?

Given a graph that has nodes that are BIDIRECTIONAL and have different weights from going to one another, meaning I can go from a->c with cost 50, and lets say c->a with cost 1/50

Meaning if I have $100 of A, then I can have 100 * 50 of currency C but if I want to go the overway around I have to do amount * (1/50)

Given an original currency node and an amount in that node, what is the maximum amount in currency C that I can get?

We basically need to find paths from a->c, but we are given the currencies that are connected such as

NodeX, NodeY (with costs to go each of the way)

example: [A,B (amount1, amount2)], [B,C (amount4, amount3)], [A,C (amount5, Amount6)]

I am having trouble with this and was wondering what is the best way to solve this? Any help would be super appreciated, thanks a lot :)

Upvotes: 0

Views: 299

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59144

The first thing you want to do is convert all your costs to logarithms, so that instead of saying that your money multiplies by 50 when you go from A to B, you add log(50) to log(money). Then negate all the weights to make them costs -- instead of multiplying money by 50 when you go from A to B, you subtract log(50) from -log(money).

Now that you're subtracting weights instead of multiplying them, they work just like costs and you have a much more normal shortest path problem: The shortest path through the graph of -log(weight)s produces the highest possible money multiplier.

You can use the Floyd Warshall algorithm to find the shortest paths between all pairs of nodes simultaneously. Note that you have a directed graph, since the edges between each pair are different in opposite directions.

This algorithm will fail if there are negative cycles in the graph. These represent cyclic paths that you could take from one node around and back to itself, while ending up with more money than you started with. Since you could go around such a path as many times as you like, there would be no maximum achievable amount.

Upvotes: 1

Related Questions