BF算法的实际应用 套汇

字数统计632阅读时长5分阅读次数

如果没接触过bf算法，先看看它的介绍吧？
bellman ford算法百度百科介绍

图中的加权有向边代表汇率，我们可以发现如果把 100 单位的货币 A 换成 B，再换成 C，最后换回 A，就可以得到 100×0.9×0.8×1.4 = 100.8 单位的 A！
如果交易的金额大一些的话，赚的钱是很可观的，这种空手套白狼的操作就是套汇。
现实中交易会有种种限制，而且市场瞬息万变，但是套汇的利润还是很高的，关键就在于如何快速找到这种套汇机会呢？
在这里插入图片描述

借助图的抽象，我们发现套汇机会其实就是一个环，且这个环上的权重之积大于 1，只要在顺着这个环交易一圈就能空手套白狼。
图论中有一个经典算法叫做 Bellman-Ford 算法，可以用于寻找负权重环。对于我们说的套汇问题，可以先把所有边的权重 w 替换成 -ln(w)，这样「寻找权重乘积大于 1 的环」就转化成了「寻找权重和小于 0 的环」
就可以使用 Bellman-Ford 算法在 O(EV) 的时间内寻找负权重环，也就是寻找套汇机会。

Bellman-Ford 伪代码理解

1
2
3
4
5
6
7
8
9
10
11
12
bool Bellman-Ford(G,w,s)        //图G ，边集 函数 w ，s为源点
  for each vertex v ∈ V(G):     //初始化距离源点距离均为无穷大
    d[v] ←+∞
  d[s] ←0                       //源点距离自身为0
  for i = 1 → |V|:              //松弛操作需要重复多次
    for each edge (u,v) ∈ E(G):
      if d[v] > d[u] + w(u,v):
        d[v] = d[u] + w(u,v)
  for each edge(u,v) ∈ E(G):    //判断是否存在负权环路
    if d[v] > d[u] + w(u,v):
      return false
  return true

SPFA实际上是用队列对bf的优化，思路差不多

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int SPFA(int s) {
     queue<int> q; 
     bool inq[maxn] = {false}; 
     for(int i = 1; i <= N; i++) dis[i] = 2147483647; 
     dis[s] = 0; 
     q.push(s); inq[s] = true; 
     while(!q.empty()) { 
         int x = q.front(); q.pop(); 
         inq[x] = false;
         for(int i = front[x]; i !=0 ; i = e[i].next) {
             int k = e[i].v;
             if(dis[k] > dis[x] + e[i].w) {
                 dis[k] = dis[x] + e[i].w;
                 if(!inq[k]) {
                     inq[k] = true;
                     q.push(k);
                 }
             }
         }
     }
     for(int i =  1; i <= N; i++) cout << dis[i] << ' ';
     cout << endl;
     return 0;
 }