Dijkstra 算法解析

算法, 贪心
loading...

Dijkstra 算法解析

简介

Dijkstra 算法是一种用于计算单源最短路径的经典算法，由计算机科学家 Edsger Dijkstra 提出。它能够解决带权有向图中的最短路径问题，广泛应用于网络路由、地图导航等领域。本文将详细解析 Dijkstra 算法的工作原理、实现步骤以及如何在实际中使用该算法。


1. Dijkstra 算法概述

Dijkstra 算法的核心思想是逐步确定从起点到其他节点的最短路径，直到所有节点的最短路径都被确定。它是一种贪心算法，每次选择距离起点最近的节点来更新其他节点的路径。


2. 算法步骤

假设我们有一个图 G，包含若干个节点和边。每条边都有一个权重，表示从一个节点到另一个节点的代价。Dijkstra 算法的步骤如下：

初始化

设定源点 s 的最短路径为 0，其他所有节点的最短路径为无穷大。
将所有节点标记为未访问。

选取当前节点

从未访问的节点中选择一个距离源点最近的节点 u，将其标记为已访问。

更新邻接节点

对于当前节点 u 的每一个邻接节点 v，检查通过 u 到达 v 是否能够得到更短的路径。如果能，更新 v 的最短路径。

重复步骤 2 和 3

重复选取最短路径节点并更新邻接节点的过程，直到所有节点的最短路径都确定。

终止条件

所有节点都已访问或者没有可达节点。


3. 算法执行过程详解

下面通过一个具体例子详细说明 Dijkstra 算法的执行过程。考虑以下带权有向图：

1
2
3
4
5
6
7
text
    A --2--> B
    |       
   1|      
    |     
    v    
    C --1--> D

假设源点为节点 A，我们需要计算从 A 到所有其他节点的最短路径。

初始化阶段：

设置 A 的距离为 0

设置 B、C、D 的距离为无穷大 (∞)

所有节点标记为未访问

执行过程：

步骤 当前节点 更新过程 距离数组
初始 - - (0, ∞, ∞, ∞)
1 A 通过 A 更新 B 和 C (0, 2, 1, ∞)
2 C 通过 C 更新 D (0, 2, 1, 2)
3 B 无更新 (0, 2, 1, 2)
4 D 无更新 (0, 2, 1, 2)

4. 算法时间复杂度

Dijkstra 算法的时间复杂度取决于实现方式。使用邻接矩阵和普通数组实现时，时间复杂度为 O(V²)，其中 V 是图中的节点数。使用优先队列（如二叉堆）优化后，时间复杂度可以降为 O((V + E) log V)，其中 E 是图中的边数。


5. 代码实现

以下是 Dijkstra 算法的 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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
package main

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

// 定义图的节点和边结构
type Edge struct {
	to     int
	weight int
}

// 定义图结构
type Graph struct {
	nodes int
	edges map[int][]Edge
}

// 优先队列相关定义
type Item struct {
	node     int
	priority int
	index    int
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].priority < pq[j].priority
}

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{} {
	n := len(*pq)
	item := (*pq)[n-1]
	(*pq)[n-1] = nil  
	item.index = -1
	*pq = (*pq)[:n-1]
	return item
}

func (pq *PriorityQueue) update(item *Item, priority int) {
	item.priority = priority
	heap.Fix(pq, item.index)
}

// Dijkstra 算法实现（使用优先队列优化）
func Dijkstra(graph Graph, start int) ([]int, []int) {
	dist := make([]int, graph.nodes)
	prev := make([]int, graph.nodes) // 用于记录最短路径
    
    // 初始化距离和前驱节点
	for i := 0; i < graph.nodes; i++ {
		dist[i] = math.MaxInt32
		prev[i] = -1
	}
	dist[start] = 0

    // 创建优先队列
	pq := make(PriorityQueue, 0)
	heap.Push(&pq, &Item{
		node:     start,
		priority: 0,
	})

    // 主循环
	for pq.Len() > 0 {
		item := heap.Pop(&pq).(*Item)
		u := item.node

        // 遍历所有邻接边
		for _, edge := range graph.edges[u] {
			v := edge.to
			alt := dist[u] + edge.weight
			if alt < dist[v] {
				dist[v] = alt
				prev[v] = u
				heap.Push(&pq, &Item{
					node:     v,
					priority: alt,
				})
			}
		}
	}

	return dist, prev
}

// 重建最短路径
func getPath(prev []int, target int) []int {
	path := make([]int, 0)
	for target != -1 {
		path = append([]int{target}, path...)
		target = prev[target]
	}
	return path
}

func main() {
	// 创建示例图
	graph := Graph{
		nodes: 4,
		edges: make(map[int][]Edge),
	}
	
	// 添加边
	graph.edges[0] = []Edge{{1, 2}, {2, 1}}
	graph.edges[1] = []Edge{{2, 3}}
	graph.edges[2] = []Edge{{3, 1}}
	graph.edges[3] = []Edge{}

	start := 0
	dist, prev := Dijkstra(graph, start)
	
	fmt.Printf("从节点 %d 到其他节点的最短距离:\n", start)
	for i, d := range dist {
		fmt.Printf("到节点 %d: %d\n", i, d)
	}
	
	fmt.Printf("\n最短路径示例:\n")
	for i := 1; i < graph.nodes; i++ {
		path := getPath(prev, i)
		fmt.Printf("到节点 %d 的路径: %v\n", i, path)
	}
}

6. 总结

Dijkstra 算法是一种经典的最短路径算法，它能够有效地解决单源最短路径问题。在理解该算法时，注意它的贪心思想和逐步更新路径的方式。通过优化数据结构，Dijkstra 算法可以在大规模图中高效运行。


7. 使用示例

LeetCode 743: 网络延迟时间

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

题目描述

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

题解

图的构建

  • 使用邻接表的形式表示图，构建图的边以及每条边的权重。
Dijkstra 算法
  • 初始化源节点 K 的时间为 0，其他节点的时间为无穷大（表示尚未到达）。
  • 使用优先队列（最小堆）来选取当前最短时间的节点。
  • 遍历所有节点，更新其邻接节点的最短时间。
结果判定
  • 遍历所有节点的最短时间，如果有节点的最短时间为无穷大，说明该节点无法接收到信号，返回 -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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
package main

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

// 优先队列中的元素
type Item struct {
	node     int     // 当前节点
	dist     float64 // 当前节点的最短距离
}

// 最小堆实现
type MinHeap []*Item

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].dist < h[j].dist }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(*Item))
}

func (h *MinHeap) Pop() interface{} {
	n := len(*h)
	x := (*h)[n-1]
	*h = (*h)[:n-1]
	return x
}

// 网络延迟时间
func networkDelayTime(times [][]int, n, k int) int {
	// 1. 构建图
	graph := make([][][2]int, n+1) // 图的邻接表，graph[i] = [(v, w), ...]
	for _, time := range times {
		u, v, w := time[0], time[1], time[2]
		graph[u] = append(graph[u], [2]int{v, w})
	}

	// 2. Dijkstra 算法
	dist := make([]float64, n+1)
	for i := 1; i <= n; i++ {
		dist[i] = math.Inf(1) // 初始化为无穷大
	}
	dist[k] = 0

	h := &MinHeap{}
	heap.Push(h, &Item{node: k, dist: 0})
	visited := make([]bool, n+1)

	for h.Len() > 0 {
		// 取出当前最短的节点
		item := heap.Pop(h).(*Item)
		node := item.node
		if visited[node] {
			continue
		}
		visited[node] = true

		// 遍历当前节点的邻接节点
		for _, neighbor := range graph[node] {
			v, w := neighbor[0], neighbor[1]
			if dist[node]+float64(w) < dist[v] {
				dist[v] = dist[node] + float64(w)
				heap.Push(h, &Item{node: v, dist: dist[v]})
			}
		}
	}

	// 3. 查找最短时间中的最大值
	maxTime := 0.0
	for i := 1; i <= n; i++ {
		if dist[i] == math.Inf(1) {
			return -1 // 存在无法到达的节点
		}
		maxTime = math.Max(maxTime, dist[i])
	}

	return int(maxTime)
}

func main() {
	// 示例
	times := [][]int{
		{2, 1, 1},
		{2, 3, 1},
		{3, 4, 1},
	}
	n := 4
	k := 2
	fmt.Println(networkDelayTime(times, n, k)) // 输出 2
}