迪杰斯特拉（Dijkstra）最短路径算法原理、实现与证明

最近研究 DeFi 套利时，发现不少经典策略都与图论算法紧密相关，其中经典的 Dijkstra 最短路径算法成为理解其他进阶算法的关键。尽管网上已有大量关于该算法的教材、资料和讲解，但我仍然花费了不少精力搜集、梳理和学习。

这篇博客一方面记录我的学习过程，帮自己加深理解、方便后续查阅；另一方面也希望能帮到同样正在学习该算法的人，争取通过看这一篇文章就能吃透所有关键细节，不用耗费过多精力四处找资料。

问题定义

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

• \(V\) 是图中所有节点的集合
• \(E\) 是图中所有边的集合
• 对于任意边 \((u, v) \in E\)，权重 \(w(u, v) \geq 0\)

指定一个源点 \(s \in V\)，求 \(s\) 到图中所有其他节点 \(v \in V\) 的最短路径长度（即路径上所有边权重之和的最小值）。

算法思想

Dijkstra 算法的基本思想是贪心策略。

假设我们要从源点 \(s\) 出发去另一个点 \(t\)，一开始对周围环境一无所知。Dijkstra 的做法是：

1. 先把所有从 \(s\) 出发能直接到达的节点都探一遍，记录到达这些节点的距离
2. 然后走到离 \(s\) 最近的那个节点
3. 从这个节点继续探索，看看能到达哪些新节点，或者能不能找到更短的路径到达已探索过的节点
4. 如果发现更短的路径，就更新距离记录（这叫"松弛操作"）
5. 重复以上过程，直到所有节点都被探索完

这个贪心策略的神奇之处在于：每次选择距离最近的未确定节点时，当前找到的路径就是这个节点的真实最短路径。这是算法正确性的关键，后续我们会证明这一点。

算法流程

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

• 距离数组 \(dist\)：\(dist[v]\) 表示算法运行过程中，当前已知的从源点 \(s\) 到节点 \(v\) 的最短路径长度。初始时 \(dist[s] = 0\)，其余节点的 \(dist[v] = +\infty\)（表示初始状态不可达）

• 已确定集 \(S\)：存储已找到最短路径的节点集合，初始时 \(S = \emptyset\)（空集）

• 松弛操作（Relaxation）：对于边 \((u, v)\)，若 \(dist[v] > dist[u] + w(u, v)\)，说明发现了一条到 \(v\) 更短的路径，更新 \(dist[v] = dist[u] + w(u, v)\)

为了提高算法效率，通常采用邻接表存储图结构，配合最小堆快速筛选出"当前距离最近的未确定节点"。

步骤 1：初始化

• 初始化距离数组 \(dist\)：\(dist[s] = 0\)，其余 \(dist[v] = +\infty\)
• 初始化最小堆：存储二元组 \((dist[v], v)\)，初始时将 \((0, s)\) 入堆
• 初始化已访问标记数组（替代集合 \(S\)）：\(visited[v] = false\)，表示节点未被确定最短路径

步骤 2：迭代处理

当堆不为空时，重复以下操作：

1. 弹出堆顶节点 \((d, u)\)：这是当前未确定节点中距离源点最近的节点
2. 跳过已确定节点：若 \(visited[u] = true\)，说明该节点的最短路径已确定，直接跳过（避免堆中冗余条目的重复处理）
3. 标记为已确定：标记 \(visited[u] = true\)，将 \(u\) 归入已确定集 \(S\)
4. 松弛邻接边：遍历 \(u\) 的所有邻接节点 \(v\)，对于每条边 \((u, v)\)，若 \(dist[v] > dist[u] + w(u, v)\)，说明发现一条途径 \(u\) 到达 \(v\) 的更短路径，执行松弛操作，更新 \(dist[v] = dist[u] + w(u, v)\)，\(v\) 可能成为距离 \(s\) 最近的潜在节点，所以将 \((dist[v], v)\) 入堆

步骤 3：结果输出

当堆为空时，距离数组 \(dist\) 中存储的就是源点 \(s\) 到所有节点的最短路径长度（不可达节点的距离为初始值 \(+\infty\)）。

算法示例

为了让流程更直观，我们用一个具体例子来演示算法执行过程。考虑一个无向图 \(G = (V, E)\)，其中：

• 节点集合 \(V = \{1, 2, 3, 4, 5, 6\}\)（用编号 0, 1, 2, 3, 4, 5 表示）
• 边及权重如下：
• \(1-2\)（权重 7）
• \(1-3\)（权重 9）
• \(1-6\)（权重 14）
• \(2-3\)（权重 10）
• \(2-4\)（权重 15）
• \(3-4\)（权重 11）
• \(3-6\)（权重 2）
• \(4-5\)（权重 6）
• \(5-6\)（权重 9）

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

最终结果：\(dist = [0, 7, 9, 20, 20, 11]\)，对应源点 \(1\) 到 \(2, 3, 4, 5, 6\) 的最短路径长度。

可以验证一下：

• \(1-2\)：直接路径，长度 7 ✓
• \(1-3\)：直接路径，长度 9 ✓
• \(1-4\)：\(1-3-4\)，长度 9+11=20（比 1-2-4 的 7+15=22 更短）✓
• \(1-5\)：\(1-3-6-5\)，长度 9+2+9=20 ✓
• \(1-6\)：\(1-3-6\)，长度 9+2=11（比直接的 14 更短）✓

算法的时间复杂度主要取决于图的存储方式和优先队列的实现方式。示例中使用邻接表+最小堆的实现方式，每个节点最多入堆和出堆一次，堆操作时间为 \(O(\log V)\)，所以这部分是 \(O(V \log V)\)；每条边最多触发一次松弛操作和入堆，所以这部分是 \(O(E \log V)\)，总时间复杂度为 \(O((V+E)\log V)\)。

算法证明

理解 Dijkstra 算法的关键，在于能够证明其正确性。根据前文说明，只要证明：当节点 \(u\) 被加入已确定集 \(S\) 时，其距离 \(dist[u]\) 等于源点 \(s\) 到 \(u\) 的真实最短路径长度 \(\delta(u)\)，即可说明算法的运行结果是正确的。

先定义几个符号：

• \(\delta(u)\)：源点 \(s\) 到节点 \(u\) 的真实最短路径长度（客观值，与算法无关）
• \(dist[u]\)：算法维护的当前距离（迭代过程中的近似值）

根据定义，显然有 \(dist[u] \geq \delta(u)\)。我们的目标是证明当 \(u \in S\) 时，\(dist[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（迭代不变式）

在算法的任意迭代步骤中，对于所有 \(u \in S\)，都有 \(dist[u] = \delta(u)\)。

证明：用数学归纳法。初始时 \(S = \emptyset\)，空集自然满足"所有元素都符合条件"，不变式成立。假设前 \(k\) 次迭代后，\(S\) 中所有节点均满足 \(dist[u] = \delta(u)\)。现在分析第 \(k+1\) 次迭代：

算法从 \(V \setminus S\) 中选择 \(u\)，使得：

现在假设 \(dist[u] > \delta(u)\)，由于 \(\delta(u)\) 是真实最短路径长度，其对应的一条最短路径\(P = s \to \dots \to x \to y \to \dots \to u\)。

根据 \(S\) 与 \(V \setminus S\) 的划分，路径 \(P\) 从 \(S\) 中的 \(s\) 出发，到 \(V \setminus S\) 中的 \(u\) 结束，必然存在一个"分界点"——即路径上最后一个属于 \(S\) 的节点 \(x\)，以及第一个属于 \(V \setminus S\) 的节点 \(y\)（\(x \to y\) 是路径上的一条边）。

基于此，我们进行推导：

1. 由归纳假设，\(x \in S\) 故 \(dist[x] = \delta(x)\)

2. 由引理 1（三角不等式），\(\delta(y) \leq \delta(x) + w(x, y) = dist[x] + w(x, y)\)

3. 算法处理 \(x\) 时（已加入 \(S\)），会对 \(y\) 执行松弛操作，因此 \(dist[y] \leq dist[x] + w(x, y)\)，又 \(s \to y\) 至少有一条最短路径必经 \(x\)（否则就有比 \(P\) 更短的路径了），所以松弛操作后实际已有 \(dist[y] = \delta(y)\)

4. 由于 \(y\) 在最短路径 \(P\) 上，且路径权重非负，故 \(\delta(y) \leq \delta(u)\)

5. 结合步骤 3 和 4，得 \(dist[y] = \delta(y) \leq \delta(u)\)。又由假设 \(dist[u] > \delta(u)\)，因此 \(dist[y] < dist[u]\)

6. 但 \(y \in V \setminus S\)，这与公式 (2) "\(u\) 是\(V \setminus S\) 中 \(dist\) 最小的节点"矛盾！

因此假设 \(dist[u] > \delta(u)\) 不成立，所以只能有 \(dist[u] = \delta(u)\)。

定理（算法正确性）

定理：当算法终止时（\(S = V\)），对于所有 \(v \in V\)，有 \(dist[v] = \delta(v)\)。

证明：算法终止时所有节点均加入 \(S\)，由引理 2，所有节点的 \(dist[v] = \delta(v)\)，即距离数组存储的是源点到所有节点的真实最短路径长度。

算法实现

下面我们用 Go 语言实现 Dijkstra 算法，采用邻接表存储图，结合标准库的 container/heap 包实现最小堆。

package main

import (
    "container/heap"
    "fmt"
    "math"
)

// Edge 表示图的边（目标节点+权重）
type Edge struct {
    to     int // 目标节点（节点用整数编号）
    weight int // 边权（非负）
}

// Graph 邻接表表示的图
type Graph struct {
    adj []*[]Edge // adj[u] 存储节点 u 的所有邻接边
}

// NewGraph 初始化图（n 为节点数）
func NewGraph(n int) *Graph {
    adj := make([]*[]Edge, n)
    for i := range adj {
        edges := make([]Edge, 0)
        adj[i] = &edges
    }
    return &Graph{adj: adj}
}

// AddEdge 向图中添加无向边 u-v（权重 w）
func (g *Graph) AddEdge(u, v, w int) error {
    if u < 0 || v < 0 || u >= len(g.adj) || v >= len(g.adj) {
        return fmt.Errorf("节点编号越界")
    }
    if w < 0 {
        return fmt.Errorf("边权不能为负（Dijkstra 算法约束）")
    }
    *g.adj[u] = append(*g.adj[u], Edge{to: v, weight: w})
    *g.adj[v] = append(*g.adj[v], Edge{to: u, weight: w})
    return nil
}

// Item 优先队列元素（距离+节点）
type Item struct {
    dist  int   // 当前距离
    node  int   // 节点编号
    index int   // 堆中的索引（用于 heap 包内部维护）
}

// PriorityQueue 最小堆（按 dist 升序排列）
type PriorityQueue []*Item

// 实现 heap.Interface 接口的必要方法
func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].dist < pq[j].dist // 最小堆
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index = i
    pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
    n := len(*pq)
    item := x.(*Item)
    item.index = n
    *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    item.index = -1 // 标记已弹出
    *pq = old[0 : n-1]
    return item
}

// Dijkstra 求解单源最短路径（s 为源点）
func (g *Graph) Dijkstra(s int) ([]int, error) {
    n := len(g.adj)
    if s < 0 || s >= n {
        return nil, fmt.Errorf("源点编号越界")
    }

    // 初始化距离数组：用 MaxInt32 表示 +∞（避免溢出）
    dist := make([]int, n)
    for i := range dist {
        dist[i] = math.MaxInt32
    }
    dist[s] = 0

    // 初始化优先队列并推入源点
    pq := make(PriorityQueue, 0)
    heap.Init(&pq)
    heap.Push(&pq, &Item{dist: 0, node: s})

    // 标记节点是否已确定最短路径（替代集合 S）
    visited := make([]bool, n)

    // 迭代处理节点
    for pq.Len() > 0 {
        // 弹出当前距离最近的未确定节点
        item := heap.Pop(&pq).(*Item)
        u := item.node
        currentDist := item.dist

        // 跳过已确定最短路径的节点（堆中冗余条目）
        if visited[u] {
            continue
        }

        // 标记为已确定
        visited[u] = true

        // 遍历邻接边，执行松弛操作
        for _, edge := range *g.adj[u] {
            v := edge.to
            w := edge.weight

            // 松弛条件：通过 u 到 v 的路径比当前记录更短
            if dist[v] > dist[u]+w {
                dist[v] = dist[u] + w
                // 将更新后的节点入堆
                heap.Push(&pq, &Item{dist: dist[v], node: v})
            }
        }
    }

    return dist, nil
}

func main() {
    // 构建示例无向图
    // 节点：0=1, 1=2, 2=3, 3=4, 4=5, 5=6
    g := NewGraph(6)
    _ = g.AddEdge(0, 1, 7)  // 1-2 (7)
    _ = g.AddEdge(0, 2, 9)  // 1-3 (9)
    _ = g.AddEdge(0, 5, 14) // 1-6 (14)
    _ = g.AddEdge(1, 2, 10) // 2-3 (10)
    _ = g.AddEdge(1, 3, 15) // 2-4 (15)
    _ = g.AddEdge(2, 3, 11) // 3-4 (11)
    _ = g.AddEdge(2, 5, 2)  // 3-6 (2)
    _ = g.AddEdge(3, 4, 6)  // 4-5 (6)
    _ = g.AddEdge(4, 5, 9)  // 5-6 (9)

    // 求解源点 1（节点 0）到所有节点的最短路径
    dist, err := g.Dijkstra(0)
    if err != nil {
        fmt.Printf("算法执行失败：%v\n", err)
        return
    }

    fmt.Println("源点 1 到各节点的最短路径长度：", dist)
    // 输出：源点 1 到各节点的最短路径长度： [0 7 9 20 20 11]
}

算法局限

Dijkstra 算法有一个重要限制：不能处理负边权。如果图中存在负权边，贪心策略可能失效。这是因为当前距离最近的节点，其最短路径可能还需要通过未确定的节点（而这些节点的距离会因为负边权变得更小）。

后续文章将讲解 Bellman-Ford 算法。该算法能处理含负边权的图，还可顺带检测图中的负权环；而负权环在金融场景中，等价于环形套利机会（即通过一组循环交易可获取无风险收益的机会）。

-- EOF --