【软件】行动手册 🚩
Graph data structure
Finding arbitrage
Bellman Ford Algorithm
我们发现了一个术语叫 predecessor chain，这很重要。
运行结果：
【算法】算法描述Last updated
Last updated
打印"负权环"以显示套利机会。
我们使用"前驱链"打印周期。
现在我们有了可以进一步放松的边缘，我们已经找到了该边缘的源顶点和目标顶点。
让我们从源顶点开始，然后返回，
直到您再次看到源顶点或在打印"负权环"时"前驱链"已经向我们显示的任何其他顶点。from typing import Tuple, List
from math import log
rates = [
[1, 0.23, 0.25, 16.43, 18.21, 4.94],
[4.34, 1, 1.11, 71.40, 79.09, 21.44],
[3.93, 0.90, 1, 64.52, 71.48, 19.37],
[0.061, 0.014, 0.015, 1, 1.11, 0.30],
[0.055, 0.013, 0.014, 0.90, 1, 0.27],
[0.20, 0.047, 0.052, 3.33, 3.69, 1],
]
currencies = ('PLN', 'EUR', 'USD', 'RUB', 'INR', 'MXN')
def negate_logarithm_convertor(graph: Tuple[Tuple[float]]) -> List[List[float]]:
''' log of each rate in graph and negate it'''
result = [[-log(edge) for edge in row] for row in graph]
return result
def arbitrage(currency_tuple: tuple, rates_matrix: Tuple[Tuple[float, ...]]):
''' Calculates arbitrage situations and prints out the details of this calculations'''
trans_graph = negate_logarithm_convertor(rates_matrix)
# Pick any source vertex -- we can run Bellman-Ford from any vertex and get the right result
source = 0
n = len(trans_graph)
min_dist = [float('inf')] * n
pre = [-1] * n
min_dist[source] = source
# 'Relax edges |V-1| times'
for _ in range(n-1):
for source_curr in range(n):
for dest_curr in range(n):
if min_dist[dest_curr] > min_dist[source_curr] + trans_graph[source_curr][dest_curr]:
min_dist[dest_curr] = min_dist[source_curr] + trans_graph[source_curr][dest_curr]
pre[dest_curr] = source_curr
# if we can still relax edges, then we have a negative cycle
for source_curr in range(n):
for dest_curr in range(n):
if min_dist[dest_curr] > min_dist[source_curr] + trans_graph[source_curr][dest_curr]:
# negative cycle exists, and use the predecessor chain to print the cycle
print_cycle = [dest_curr, source_curr]
# Start from the source and go backwards until you see the source vertex again or any vertex that already exists in print_cycle array
while pre[source_curr] not in print_cycle:
print_cycle.append(pre[source_curr])
source_curr = pre[source_curr]
print_cycle.append(pre[source_curr])
print("Arbitrage Opportunity: \n")
print(" --> ".join([currencies[p] for p in print_cycle[::-1]]))
if __name__ == "__main__":
arbitrage(currencies, rates)
# Time Complexity: O(N^3)
# Space Complexity: O(N^2)