StackOveflow!

I am trying to create an Arbitrage strategy to get a better understanding of how to work with graphs. I am using python.
Graph:

Table format:

Task: find path of currency trading where we will get max profit. For example: USD->EUR(0.75), EUR->GBP(2),GBP->USA(0.7): 0.75*2*0.7=1.05, so we are getting 5% profit.

I thought that I can modify Floyd–Warshall algorithm or the Dijkstra algorithm to find not the shortest but the longest path. But it failed...
What algos are used for such tasks?

CodePudding user response：

The path that is the most expensive is found by

• find most expensive edge
• loop E over edges
  • subtract cost of most expensive edge from cost of E
  • set cost of edge to absolute value
  • end loop
• loop over all pairs of vertices
  • apply Dijkstra and keep best result.
  • end loop