Bellman-Ford 算法

算法, 最短路径
loading...

Bellman-Ford 算法解析

Bellman-Ford 算法是一种用于计算单源最短路径的算法，适用于图中存在负权边的情况。它能够解决存在负权环的图，并且在处理时较为简单。本文将详细介绍 Bellman-Ford 算法的原理、步骤及为什么需要进行 n-1 次松弛操作。

1. 算法简介

Bellman-Ford 算法基于松弛操作（Relaxation）来找到最短路径。松弛操作是指通过一条边更新节点的最短路径估计值，只有当新的路径更短时才更新。算法通过对每一条边进行 n-1 次松弛操作，最终得到图中所有节点的最短路径。

2. 算法步骤

  1. 初始化：
    将源节点到源节点的距离设为 0，其他节点到源节点的距离设为无穷大。

  2. 松弛操作：
    对图中的每一条边进行松弛操作 n-1 次。在每次松弛时，如果当前路径通过某条边可以提供更短的路径，则更新目标节点的距离。

  3. 检查负权环：
    再次进行一次松弛操作，如果有边的松弛操作仍然可以更新距离，说明图中存在负权环。


3. 为什么 Bellman-Ford 需要进行 n-1 次松弛操作？

3.1 最短路径的性质

在图中，最短路径是由一系列的边组成的。对于一个包含 n 个节点的图，最短路径最多只会包含 n-1 条边。为什么是 n-1 条边？这是因为最短路径不会包含环，且在最短路径的计算中，最多需要经过图中的 n-1 条边。

3.2 逐步松弛过程

  • 第一次松弛操作：每个节点只能通过一条边连接到源节点。
  • 第二次松弛操作：每个节点可以通过两条边连接到源节点，依此类推，最多 n-1 次松弛操作，每次都能够计算并更新通过更多边的最短路径。

3.3 为什么不是 n 次？

如果你进行了 n 次松弛操作，实际上不再有意义。原因是，最短路径最多只有 n-1 条边。如果在第 n 次松弛操作时，仍然能够更新某个节点的最短路径，说明图中存在负权环。负权环的存在使得最短路径可以不断缩短，因此无法计算出正确的最短路径。

3.4 松弛操作的核心

在 Bellman-Ford 算法中，每一次松弛操作都会将当前路径更新为最短路径。经过 n-1 次松弛操作后，我们能够保证所有节点的最短路径已经被正确计算。如果图中没有负权环，所有节点的最短路径已经找出，不需要继续松弛。


4. 负权环的检测

Bellman-Ford 算法的一个重要特性是能够检测图中的负权环。在进行 n-1 次松弛操作之后，如果再进行一次松弛操作，并且某条边的最短路径仍然可以被更新，说明图中存在负权环。负权环导致最短路径无法稳定，因此 Bellman-Ford 算法通过这种方式来检测图中是否存在负权环。


5. 示例代码

下面是 Bellman-Ford 算法的 Go 语言实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
package main

import (
    "fmt"
    "math"
)

type Edge struct {
    u, v, weight int
}

func bellmanFord(n, start int, edges []Edge) ([]int, error) {
    dist := make([]int, n)
    for i := range dist {
        dist[i] = math.MaxInt32
    }
    dist[start] = 0

    for i := 0; i < n-1; i++ {
        for _, edge := range edges {
            if dist[edge.u] != math.MaxInt32 && dist[edge.u]+edge.weight < dist[edge.v] {
                dist[edge.v] = dist[edge.u] + edge.weight
            }
        }
    }

    // Check for negative-weight cycles
    for _, edge := range edges {
        if dist[edge.u] != math.MaxInt32 && dist[edge.u]+edge.weight < dist[edge.v] {
            return nil, fmt.Errorf("graph contains a negative-weight cycle")
        }
    }

    return dist, nil
}

func main() {
    edges := []Edge{
        {0, 1, -1},
        {0, 2, 4},
        {1, 2, 3},
        {1, 3, 2},
        {1, 4, 2},
        {3, 2, 5},
        {3, 1, 1},
        {4, 3, -3},
    }

    dist, err := bellmanFord(5, 0, edges)
    if err != nil {
        fmt.Println(err)
    } else {
        fmt.Println("Shortest distances from source:")
        for i, d := range dist {
            fmt.Printf("Node %d: %d\n", i, d)
        }
    }
}

6. 总结

Bellman-Ford 算法是一种用于单源最短路径的经典算法，能够处理带有负权边的图，并且可以检测负权环。我们需要进行 n-1 次松弛操作来确保最短路径的正确计算，超过 n-1 次松弛操作可能会暴露负权环的存在，从而帮助我们进一步分析图的结构。


7 Bellman-Ford 使用示例

LeetCode 743: 网络延迟时间

题目要求的是：从某个节点 K 发出信号，计算信号到达所有节点的最短时间。如果某些节点无法接收到信号，返回 -1。

题目描述

给定一个图，图中的节点标号为 1 到 n，且图中的每条边都有一个信号传递时间。我们需要从源节点 K 开始，计算其他所有节点接收到信号的时间。信号从源节点传递到其他节点的时间由边的权重给定。如果有任何一个节点无法接收到信号，返回 -1。

题解

我们将采用 Bellman-Ford 算法来解决此问题，具体步骤如下：

  • 初始化：将源节点到源节点的距离设为 0，其他节点到源节点的距离设为无穷大。
  • 松弛操作：对每一条边进行 n-1 次松弛操作，以确保所有最短路径都能够正确更新。
  • 判断节点是否可达：如果有节点的最短距离仍然是无穷大，表示该节点不可达，返回 -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
package main

import (
	"fmt"
	"math"
)

// Edge 结构体表示一条有向边
type Edge struct {
	u, v, weight int
}

func networkDelayTime(times [][]int, n, k int) int {
	// 初始化图的边
	var edges []Edge
	for _, time := range times {
		edges = append(edges, Edge{u: time[0] - 1, v: time[1] - 1, weight: time[2]})
	}

	// Bellman-Ford 算法
	dist := make([]int, n)
	for i := range dist {
		dist[i] = math.MaxInt32
	}
	dist[k-1] = 0 // 源节点的距离设为 0

	// 进行 n-1 次松弛操作
	for i := 0; i < n-1; i++ {
		for _, edge := range edges {
			if dist[edge.u] != math.MaxInt32 && dist[edge.u]+edge.weight < dist[edge.v] {
				dist[edge.v] = dist[edge.u] + edge.weight
			}
		}
	}

	// 检查最短路径
	maxDist := 0
	for _, d := range dist {
		if d == math.MaxInt32 {
			return -1 // 如果某个节点不可达，返回 -1
		}
		if d > maxDist {
			maxDist = d
		}
	}

	return maxDist
}

func main() {
	// 示例：times 表示图中的边，n 是节点数，k 是源节点
	times := [][]int{
		{2, 1, 1},
		{2, 3, 1},
		{3, 4, 1},
	}
	n := 4
	k := 2

	result := networkDelayTime(times, n, k)
	fmt.Println(result) // 输出 2
}