Question

Suppose you are given a table of currency exchange rates, represented as a 2d array. Determine whether there is a possible arbitrage: that is, whether there is some sequence of trades you can make, starting with some amount a of any currency, so that you can end up with some amount greater than a of that currency.

Answer 1

from math import log

def arbitrage(table):

t_graph = [[-log(edge) for edge in row] for row in graph]

   source = 0

   n = len(t_graph)

   min_dist = [float('inf')] * n

   min_dist[source] = 0

   # Relax edges |V - 1| times

   for i in range(n - 1):

       for v in range(n):

           for w in range(n):

               if min_dist[w] > min_dist[v] + t_graph[v][w]:

                   min_dist[w] = min_dist[v] + t_graph[v][w]

   # If we can still relax edges, then we have a negative cycle

   for v in range(n):

       for w in range(n):

           if min_dist[w] > min_dist[v] + t_graph[v][w]:

               return True

return False