【算法】算法描述

世界的本质：2 * 3 = 6

无定价缺陷的货币汇率关系：2 * 3 = 6
有定价缺陷的货币汇率关系：2 * 3 > 5.9 
用环形表示有缺陷汇率关系：2 * 3 * 1/5.9 > 1 
取ln的环形有缺陷汇率关系：-ln2 + -ln3 + -ln(1/5.9) < 0，
就是一个负权环。 
然后用Bellman-Ford-Moore算法去找，时间复杂度是 O(N^3)。

你要做的是，把市场数据下载到一个服务器里，
用货币名称作为顶点V，用 -ln(汇率)作为边权E，
建立货币市场，带边权有向图 G(V,E) 的邻接矩阵，
用这个 B-F-M 算法，从图的邻接矩阵表示里面，寻找其中的套利路径。

INITIALIZE-SINGLE-SOURCE(G,s)
    for each vertex v ∈ G.V
        v.d = ∞
        v.π = NIL 
    s.d = 0
RELAX(u,v,w)
    if v.d > u.d + w(u,v)
        v.d = u.d + w(u,v)
        v.π = u 
//算法本体开始
BELLMAN-FORD-FIND-NEGATIVE-CYCLE(G,w,s)
//第一部分：初始化，引用INITIALIZE-SINGLE-SOURCE(G,s)
    INITIALIZE-SINGLE-SOURCE(G,s)
//第二部分：计算，引用RELAX(u,v,w)
    for i <- 1 to |V[G]| - 1 
        do for each edge (u,v) ∈ E[G]
            do RELAX(u,v,w) 
//第三部分：检验，FIND-NEGATIVE-CYCLE。
    for each edge (u,v) ∈ E[G]
        do if d[v] > d[u] + w(u,v)
            then mark v
                x <- v
                while π[x] is not marked 
                    do mark π[x]
                        x <- π[x]
                return marked nodes 
    return NIL