У меня есть список валют и таблица курсов валют. Учитывая 1 единицу некоторой валюты, мне нужно найти список биржевых транзакций, чтобы получить максимальное количество валют друг друга. Я знаю, что не существует циклов, которые позволили бы мне произвольно обогащаться с помощью арбитража.
Я превратил эту проблему в задачу с графом. Каждая валюта является вершиной, а возможные обменные операции - ребрами. Вес ребер минус логарифм обменного курса, поэтому задача преобразуется в задачу кратчайшего пути (минимум минус суммы логарифмов аналогичен максимизации умножения). Теперь я выполняю Белман-Форд и нахожу лучший путь измой источник в любую вершину (валюту). Время выполнения O (n ^ 3)
Мой вопрос, есть ли лучший и более быстрый алгоритм?
Спасибо!
Рон