Bellman-Ford 算法原理及其在 DeFi 套利中的应用

研究 DeFi 套利时，Bellman-Ford 算法是经典工具之一。这篇文章将详细讲解该算法的原理并通过证明其正确性加深对算法的理解，同时说明 DeFi 中的环形套利策略等价于在代币汇率图中寻找负权环。基于这一等价关系，便可应用 Bellman-Ford 算法高效定位套利机会。

问题定义

给定一个带权有向图 \(G = (V, E)\)，其中：

• \(V\) 是图中所有节点的集合
• \(E\) 是图中所有边的集合
• 对于任意边 \((u, v) \in E\)，其权重为 \(w(u, v)\) （可正可负）

指定一个源点 \(s \in V\)

1. 求源点 \(s\) 到图中所有其他节点 \(v \in V\) 的最短路径长度（若存在）
2. 若图中存在"从源点可达的负权环"，则精准检测该环（此时环上节点无最短路径）

所谓负权环，指环 \(C = v_1 \to v_2 \to \dots \to v_k \to v_1\)，满足 \(\sum_{i=1}^k w(v_i, v_{i+1}) < 0\)（其中 \(v_{k+1} = v_1\)）。若源点能到达这个环，则可以无限绕环来不断减小路径长度，此时最短路径为 \(-\infty\)

算法思想

与 Dijkstra 算法通过"优先选择当前已知距离起点最近的顶点"这一局部最优决策来求全局最短路径的贪心策略不同，Bellman-Ford 算法通过“开天眼”的方式总是选择全局最优路径。Bellman-Ford 算法在每一轮迭代中遍历所有的边，考察以该边为最后一节的路径是否比节点已记录的路径更短，如果更短就更新距离记录（这叫"松弛操作"）。

算法神奇之处在于，如果节点的真实最短路径最多包含 \(k\) 条边，那么第 \(k\) 轮迭代得到的值就是节点的真实最短路径。这是算法正确性的关键，后续我们会证明这一点。

算法流程

基于上面的思想，我们定义一些数据结构来记录状态：

• 距离数组 \(dist\)：\(dist[v]\) 表示算法运行过程中，当前已知的从源点 \(s\) 到节点 \(v\) 的最短路径长度。初始时 \(dist[s] = 0\)，其余节点的 \(dist[v] = +\infty\)（表示初始状态下不可达）
• 边列表：存储所有边 \((u, v, w)\)，其中 \(u\) 是起点，\(v\) 是终点，\(w\) 是权重

为了提高算法效率，通常采用边列表存储图结构（每个节点维护出边列表）。

步骤 1：初始化

• 初始化距离数组 \(dist\)：\(dist[s] = 0\)，其余 \(dist[v] = +\infty\)
• （可选）初始化前驱数组 \(prev\)：\(prev[v] = -1\)，用于后续重构最短路径路径

步骤 2：\(V-1\) 轮松弛迭代

循环 \(V-1\) 次，每轮遍历所有边：

1. 遍历所有边：对于每条边 \((u, v)\)，若 \(dist[u] \neq +\infty\)（\(u\) 已可达）且 \(dist[v] > dist[u] + w(u, v)\)（通过 \(u\) 到 \(v\) 更短），则执行松弛操作：更新 \(dist[v] = dist[u] + w(u, v)\)
2. 提前终止优化：若某轮松弛没有发生任何更新，说明所有最短路径已找到，可以提前终止（后续轮次也不会有更新）

步骤 3：负权环检测

• 遍历所有边 \((u, v)\) 一次：
• 若 \(dist[u] \neq +\infty\) 且 \(dist[v] > dist[u] + w(u, v)\)，说明存在"从源点可达的负权环"
• 若未找到这样的边，则 \(dist\) 数组即为源点到所有节点的最短路径长度

算法示例

为了让流程更直观，我们用一个具体例子来演示算法执行过程。

考虑一个有向图 \(G = (V, E)\)，其中：
- 节点集合 \(V = \{s, A, B, C, D\}\)（共 \(V=5\) 个节点，需执行 \(5-1=4\) 轮松弛）
- 边及权重：
- \(s \to A\)（权重 6）
- \(s \to C\)（权重 7）
- \(A \to B\)（权重 5）
- \(A \to C\)（权重 8）
- \(A \to D\)（权重 -4）
- \(B \to A\)（权重 -2）
- \(C \to B\)（权重 -3）
- \(C \to D\)（权重 9）
- \(D \to s\)（权重 2）
- \(D \to B\)（权重 7）

我们要求从源点 \(s\) 到所有其他节点的最短路径。下面是算法执行的完整过程：

初始化

\(dist = [0, +\infty, +\infty, +\infty, +\infty]\)（对应节点：\(s, A, B, C, D\)）

第 1 轮松弛

第 1 轮后：\(dist = [0, 6, 4, 7, 2]\)

第 2 轮松弛

第 2 轮后：\(dist = [0, 2, 4, 7, 2]\)

第 3 轮松弛

第 3 轮后：\(dist = [0, 2, 4, 7, -2]\)

第 4 轮松弛

第 4 轮后：\(dist\) 无变化（已完成 \(V-1\) 轮松弛）

遍历所有边，对每一条边执行松弛判断，均无法更新距离数组 \(dist\)，说明图中不存在从源点 \(s\) 可达的负权环。

最终结果：\(dist = [0, 2, 4, 7, -2]\)（\(s→A=2\)，\(s→B=4\)，\(s→C=7\)，\(s→D=-2\)）。

可以验证一下：

• \(s \to A\)：最优路径 \(s \to C \to B \to A\)，长度 \(7+(-3)+(-2)=2\) ✓
• \(s \to B\)：最优路径 \(s \to C \to B\)，长度 \(7+(-3)=4\) ✓
• \(s \to C\)：直接路径，长度 7 ✓
• \(s \to D\)：最优路径 \(s \to C \to B \to A \to D\)，长度 \(7+(-3)+(-2)+(-4)=-2\) ✓

示例算法中，外层循环执行 \(V-1\) 次，内层遍历所有边，每次 \(O(E)\)，因此总的时间复杂度为 \(O((V-1) \cdot E) = O(VE)\)。

算法证明

理解 Bellman-Ford 算法的关键，在于能够证明其正确性。需证明两点：

1. \(V-1\) 轮松弛后，可达节点的 \(dist[v] = \delta(v)\)（\(\delta(v)\) 为真实最短路径长度）
2. 第 \(V\) 轮松弛仍能更新则存在负权环。

先定义几个符号：

• \(\delta(u)\)：源点 \(s\) 到节点 \(u\) 的真实最短路径长度（客观值，与算法无关）。若 \(u\) 不可达则 \(\delta(u) = +\infty\)，若存在可达负权环则 \(\delta(u) = -\infty\)
• \(dist[u]\)：算法维护的当前距离（迭代过程中的近似值）
• \(dist_i[u]\)：第 \(i\) 轮松弛后 \(dist[u]\) 的值

根据定义，显然有 \(dist[u] \geq \delta(u)\)。我们的目标是证明当 \(u\) 可达且无负权环时，\(dist_{V-1}[u] = \delta(u)\)。

引理 1（三角不等式）

对于任意边 \((u, v) \in E\)，有：

证明：源点到 \(v\) 的最短路径有两种可能，要么经过 \(u\)，要么不经过。

• 若经过 \(u\)，则 \(\delta(v) = \delta(u) + w(u, v)\)
• 若不经过，则 \(\delta(v) < \delta(u) + w(u, v)\)（否则经过 \(u\) 的路径成了最短路径，矛盾）

因此总有 \(\delta(v) \leq \delta(u) + w(u, v)\)。

引理 2（路径长度上界性质）

在第 \(i\) 轮松弛后，对于所有节点 \(v\)，\(dist_i[v]\) 的值等于从源点 \(s\) 到 \(v\) 最多包含 \(i\) 条边的最短路径长度。

证明：用数学归纳法。\(i=0\) 时，\(dist_0[s] = 0\)（0 条边的路径），其余 \(dist_0[v] = +\infty\)（不存在 0 条边的路径），成立。假设第 \(k\) 轮后，\(dist_k[v]\) 等于从 \(s\) 到 \(v\) 的最多包含 \(k\) 条边的最短路径长度。现在分析第 \(k+1\) 轮松弛：

对于任意节点 \(v\)，从 \(s\) 到 \(v\) 的最多包含 \(k+1\) 条边的最短路径，可以分解为：从 \(s\) 到某节点 \(u\) 的最多包含 \(k\) 条边的最短路径，再加上边 \((u, v)\)。因此：

第 \(k+1\) 轮松弛会遍历所有边 \((u, v)\)，并执行 \(dist_{k+1}[v] = \min(dist_k[v], dist_k[u] + w(u, v))\)，这正是上述最小值的计算过程。因此 \(dist_{k+1}[v]\) 等于从 \(s\) 到 \(v\) 的最多包含 \(k+1\) 条边的最短路径长度。

定理（\(V-1\) 轮松弛的正确性）

定理：若节点 \(v\) 可达且图中不存在从源点可达的负权环，则 \(dist_{V-1}[v] = \delta(v)\)。

证明：由引理 2，\(dist_{V-1}[v]\) 等于从 \(s\) 到 \(v\) 的最多包含 \(V-1\) 条边的最短路径长度。由于图中无负权环，\(v\) 的最短路径必然是简单路径（不含重复节点），因此最多包含 \(V-1\) 条边（\(V\) 个节点）。所以 \(dist_{V-1}[v] = \delta(v)\)。

定理（负权环检测的正确性）

定理：若 \(V-1\) 轮松弛后，存在边 \((u, v)\) 满足 \(dist[v] > dist[u] + w(u, v)\)，则图中存在从源点可达的负权环。

证明：用反证法。假设图中不存在可达负权环，由前述定理，所有可达节点的 \(dist_{V-1}[v] = \delta(v)\)。由引理 1（三角不等式），\(\delta(v) \leq \delta(u) + w(u, v)\)，即 \(dist_{V-1}[v] \leq dist_{V-1}[u] + w(u, v)\)，与"仍能松弛"的条件 \(dist[v] > dist[u] + w(u, v)\) 矛盾，因此假设不成立，存在可达负权环。

算法实现

下面我们用 Go 语言实现 Bellman-Ford 算法，采用边列表存储图结构。

package main

import (
    "fmt"
    "math"
)

// Edge 定义边结构：起点 u→终点 v，权重 w（支持正负权）
type Edge struct {
    u      int // 起点
    v      int // 终点
    weight int // 权重
}

// Graph 定义图结构：存储节点数和边列表（邻接表法）
type Graph struct {
    vertexCount int    // 节点总数V
    edges       []Edge // 边列表E
}

// NewGraph 初始化图（n 为节点数，节点编号从 0 开始）
func NewGraph(n int) *Graph {
    return &Graph{
        vertexCount: n,
        edges:       make([]Edge, 0),
    }
}

// AddEdge 向图中添加有向边 u→v（权重 w），带节点越界校验
func (g *Graph) AddEdge(u, v, w int) error {
    if u < 0 || v < 0 || u >= g.vertexCount || v >= g.vertexCount {
        return fmt.Errorf("节点编号越界（合法范围 0<=u,v<%d）", g.vertexCount)
    }
    g.edges = append(g.edges, Edge{u: u, v: v, weight: w})
    return nil
}

// BellmanFord 求解单源最短路径，核心能力：支持负权边 + 检测可达负权环 + 输出负权环路径
// 返回：距离数组、负权环路径数组（无环则为空）、是否存在负权环、错误信息
func (g *Graph) BellmanFord(s int) ([]int, []int, bool, error) {
    n := g.vertexCount
    if s < 0 || s >= n {
        return nil, nil, false, fmt.Errorf("源点编号越界（合法范围0<=s<%d）", n)
    }

    // 1. 初始化距离数组：源点到自身为 0，其余为 +∞
    dist := make([]int, n)
    for i := range dist {
        dist[i] = math.MaxInt32
    }
    dist[s] = 0

    // 前驱节点数组，记录每个节点的最短路径前驱，用于回溯路径/提取负权环
    // prev[v] = u 表示最短路径中 u → v，初始值 -1 表示无前置节点
    prev := make([]int, n)
    for i := range prev {
        prev[i] = -1
    }

    // 2. V-1 轮松弛迭代：松弛所有边，找到所有最短路径（无负权环时最多松弛 V-1 次）
    for i := 0; i < n-1; i++ {
        updated := false // 优化：本轮无更新则提前退出，提升效率
        for _, edge := range g.edges {
            u, v, w := edge.u, edge.v, edge.weight
            if dist[u] == math.MaxInt32 { // 起点不可达，跳过松弛
                continue
            }
            // 松弛操作：更新更短路径
            if dist[v] > dist[u]+w {
                dist[v] = dist[u] + w
                prev[v] = u // 同步更新前驱节点，记录路径走向
                updated = true
            }
        }
        if !updated {
            break
        }
    }

    // 3. 负权环检测：第 V 轮仍能松弛 → 存在从源点可达的负权环
    hasNegativeCycle := false
    cycleStartNode := -1 // 记录负权环上的任意一个节点（松弛成功的节点）
    for _, edge := range g.edges {
        u, v, w := edge.u, edge.v, edge.weight
        if dist[u] == math.MaxInt32 {
            continue
        }
        // 仍可松弛，说明存在负权环，记录环上节点 v
        if dist[v] > dist[u]+w {
            hasNegativeCycle = true
            cycleStartNode = v
            break
        }
    }

    // 负权环路径提取核心逻辑
    negativeCycle := make([]int, 0) // 存储负权环的节点路径（有向）
    if hasNegativeCycle {
        // 步骤 1：从环上节点出发，回溯 n 步前驱 → 必然落到负权环的某个节点（环入口）
        // 原理：图中最多 n 个节点，回溯 n 步后一定会进入环内，避免前驱链过长导致找不到环
        entry := cycleStartNode
        for i := 0; i < n; i++ {
            entry = prev[entry]
        }

        // 步骤 2：从环入口出发，再次回溯前驱，收集所有环节点，直到回到入口
        current := entry
        negativeCycle = append(negativeCycle, current)
        for {
            current = prev[current]
            negativeCycle = append(negativeCycle, current)
            if current == entry { // 回到入口，环收集完成
                break
            }
        }
    }

    return dist, negativeCycle, hasNegativeCycle, nil
}

// 格式化输出距离结果：将极大值转为 ∞，提升可读性
func formatDist(dist []int) []string {
    res := make([]string, len(dist))
    for i, d := range dist {
        if d == math.MaxInt32 {
            res[i] = "∞"
        } else {
            res[i] = fmt.Sprintf("%d", d)
        }
    }
    return res
}

// 新增：格式化负权环路径，转为 "节点→节点→节点" 的有向格式，提升可读性
func formatCyclePath(cycle []int) string {
    if len(cycle) == 0 {
        return "无"
    }
    res := ""
    for i := len(cycle) - 1; i >= 0; i-- {
        res += fmt.Sprintf("%d", cycle[i])
        if i > 0 {
            res += "→"
        }
    }
    return res
}

func main() {
    fmt.Println("===== Case 1：无负权环 =====")
    // 节点数：5 个（编号 0-4），源点设为 0，含正权/负权边
    g1 := NewGraph(5)

    _ = g1.AddEdge(0, 1, 6)
    _ = g1.AddEdge(0, 3, 7)
    _ = g1.AddEdge(1, 2, 5)
    _ = g1.AddEdge(1, 3, 8)
    _ = g1.AddEdge(1, 4, -4)
    _ = g1.AddEdge(2, 1, -2)
    _ = g1.AddEdge(3, 2, -3)
    _ = g1.AddEdge(3, 4, 9)
    _ = g1.AddEdge(4, 0, 2)
    _ = g1.AddEdge(4, 2, 7)

    // 求解源点 0 到所有节点的最短路径（适配新增的负权环路径返回值）
    dist1, cyclePath1, hasCycle1, err1 := g1.BellmanFord(0)
    if err1 != nil {
        fmt.Printf("算法执行失败：%v\n", err1)
        return
    }
    // 格式化输出结果
    fmt.Printf("源点 0 → 各节点最短路径：%v\n", formatDist(dist1))
    fmt.Printf("图中是否存在【源点可达的负权环】：%t\n", hasCycle1)
    // 新增：输出负权环路径（无环则显示「无」）
    fmt.Printf("负权环具体路径：%s\n\n", formatCyclePath(cyclePath1))

    fmt.Println("===== Case 2：带负权环 =====")
    // 节点数：4 个（编号 0-3），包含明确的负权环 1→2→1（总权重=-1）
    g2 := NewGraph(4)
    _ = g2.AddEdge(0, 1, 1)
    _ = g2.AddEdge(1, 2, -3)
    _ = g2.AddEdge(2, 1, 1)
    _ = g2.AddEdge(1, 3, 2)
    _ = g2.AddEdge(2, 3, 1)

    // 求解源点 0 到所有节点的最短路径（适配新增的负权环路径返回值）
    dist2, cyclePath2, hasCycle2, err2 := g2.BellmanFord(0)
    if err2 != nil {
        fmt.Printf("算法执行失败：%v\n", err2)
        return
    }
    // 格式化输出结果
    fmt.Printf("源点 0 → 各节点最短路径：%v\n", formatDist(dist2))
    fmt.Printf("图中是否存在【源点可达的负权环】：%t\n", hasCycle2)
    // 新增：输出负权环路径
    fmt.Printf("负权环具体路径：%s\n", formatCyclePath(cyclePath2))
}

负权环的应用：环形套利

金融市场中，不同资产可相互兑换，因汇率差异存在一种经典套利策略：环形套利。我们定义 \(A \to B\) 为“将资产 \(A\) 兑换为资产 \(B\)”：若从资产 \(A\) 出发，经过 \(A \to B \to C \to \dots \to A\) 的环形交易后，最终持有的 \(A\) 资产数量高于初始数量，即可通过该路径实现套利。

以 DeFi 交易为例，我们可将 DEX（去中心化交易所）中的代币作为图的顶点，代币间的汇率（准确来说是汇率的自然对数的负值）作为边的权重，构建代币汇率图。

假设存在代币兑换环路 \(t_1 \to t_2 \to \dots \to t_n\)，对应汇率依次为 \(r_1, r_2, \dots, r_n\)。若初始本金为 1，绕环兑换后的最终本金为：

当 \(P > 1\) 时，说明存在套利机会。

对公式 (1) 两边取自然对数，可得：

若 \(P > 1\)，则 \(\ln(P) > 0\)；对等式两边取负号后：

若我们将代币汇率图中边的权重定义为汇率的自然对数的负值（即 \(w = -\ln(r_i)\)），则上述不等式可表示为环形路径上所有边的权重之和：

这意味着，存在套利机会的环形路径，对应图中的一个负权环。

反之亦然：图中存在负权环，就等价于对应代币兑换路径存在套利机会。

在实际开发中，首先会构建初始的代币汇率图；之后根据交易事件实时更新代币间的汇率（即图中边的权重），这一步通常会采用线下模拟计算的方式，主要原因是链上直接查询的速度可能较慢。完成汇率图更新后，运行 Bellman-Ford 算法检测图中是否存在负权环。

我们会在后续文章中展示具体的套利程序开发过程，如果感兴趣，请关注我的博客更新 👀。

-- EOF --