Dijkstra [迪杰斯特拉算法]
# 介绍
戴克斯特拉算法（英语：Dijkstra's algorithm），又译迪杰斯特拉算法，亦可不音译而称为 Dijkstra 算法。戴克斯特拉算法使用类似广度优先搜索的方法解决赋权图的单源最短路径问题。
该算法存在很多变体：戴克斯特拉的原始版本仅适用于找到两个顶点之间的最短路径，后来更常见的变体固定了一个顶点作为源结点然后找到该顶点到图中所有其它结点的最短路径，产生一个最短路径树。
该算法解决了图 上带权的单源最短路径问题。具体来说，戴克斯特拉算法设置了一顶点集合 S，在集合 S 中所有的顶点与源点 s 之间的最终最短路径权值均已确定。算法反复选择最短路径估计最小的点 并将 u 加入 S 中。该算法常用于路由算法或者作为其他图算法的一个子模块。
应当注意，绝大多数的戴克斯特拉算法不能有效处理带有负权边的图。
戴克斯特拉算法在计算机科学的人工智能等领域也被称为均一开销搜索，并被认为是最良优先搜索（英语：best-first search）的一个特例。
# 演示
戴克斯特拉算法运行演示（找到 A，B 之间的最短路），本算法每次取出未访问结点中距离最小的，用该结点更新其他结点的距离。在演示过程中访问过的结点会被标为红色。
动画：
戴克斯特拉算法:
# 实现
# JavaScript
/**
* Author: Samarth Jain
* Dijkstra's Algorithm implementation in JavaScript
* Dijkstra's Algorithm calculates the minimum distance between two nodes.
* It is used to find the shortest path.
* It uses graph data structure.
*/
function createGraph (V, E) {
// V - Number of vertices in graph
// E - Number of edges in graph (u,v,w)
const adjList = [] // Adjacency list
for (let i = 0; i < V; i++) {
adjList.push([])
}
for (let i = 0; i < E.length; i++) {
adjList[E[i][0]].push([E[i][1], E[i][2]])
adjList[E[i][1]].push([E[i][0], E[i][2]])
}
return adjList
}
function dijkstra (graph, V, src) {
const vis = Array(V).fill(0)
/**
* The first value in the array determines the minimum distance and the
* second value represents the parent node from which the minimum distance has been calculated
*/
const dist = []
for (let i = 0; i < V; i++) dist.push([10000, -1])
dist[src][0] = 0
for (let i = 0; i < V - 1; i++) {
let mn = -1
for (let j = 0; j < V; j++) {
if (vis[j] === 0) {
if (mn === -1 || dist[j][0] < dist[mn][0]) mn = j
}
}
vis[mn] = 1
for (let j = 0; j < graph[mn].length; j++) {
const edge = graph[mn][j]
if (vis[edge[0]] === 0 && dist[edge[0]][0] > dist[mn][0] + edge[1]) {
dist[edge[0]][0] = dist[mn][0] + edge[1]
dist[edge[0]][1] = mn
}
}
}
return dist
}
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
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
迪杰斯特拉算法寻最短路径:
// starting at s
function solve (graph, s) {
const solutions = {}
solutions[s] = []
solutions[s].dist = 0
while (true) {
let p = null
let neighbor = null
let dist = Infinity
for (const n in solutions) {
if (!solutions[n]) { continue }
const ndist = solutions[n].dist
const adj = graph[n]
for (const a in adj) {
if (solutions[a]) { continue }
const d = adj[a] + ndist
if (d < dist) {
p = solutions[n]
neighbor = a
dist = d
}
}
}
// no more solutions
if (dist === Infinity) {
break
}
// extend parent's solution path
solutions[neighbor] = p.concat(neighbor)
// extend parent's cost
solutions[neighbor].dist = dist
}
return solutions
}
// // create graph
// const graph = {}
// const layout = {
// R: ['2'],
// 2: ['3', '4'],
// 3: ['4', '6', '13'],
// 4: ['5', '8'],
// 5: ['7', '11'],
// 6: ['13', '15'],
// 7: ['10'],
// 8: ['11', '13'],
// 9: ['14'],
// 10: [],
// 11: ['12'],
// 12: [],
// 13: ['14'],
// 14: [],
// 15: []
// }
// // convert uni-directional to bi-directional graph
// let graph = {
// a: {e:1, b:1, g:3},
// b: {a:1, c:1},
// c: {b:1, d:1},
// d: {c:1, e:1},
// e: {d:1, a:1},
// f: {g:1, h:1},
// g: {a:3, f:1},
// h: {f:1}
// };
// for (const id in layout) {
// if (!graph[id]) { graph[id] = {} }
// layout[id].forEach(function (aid) {
// graph[id][aid] = 1
// if (!graph[aid]) { graph[aid] = {} }
// graph[aid][id] = 1
// })
// }
// // choose start node
// const start = '10'
// // get all solutions
// const solutions = solve(graph, start)
// // for s in solutions..
// ' -> ' + s + ': [' + solutions[s].join(', ') + '] (dist:' + solutions[s].dist + ')'
// From '10' to
// -> 2: [7, 5, 4, 2] (dist:4)
// -> 3: [7, 5, 4, 3] (dist:4)
// -> 4: [7, 5, 4] (dist:3)
// -> 5: [7, 5] (dist:2)
// -> 6: [7, 5, 4, 3, 6] (dist:5)
// -> 7: [7] (dist:1)
// -> 8: [7, 5, 4, 8] (dist:4)
// -> 9: [7, 5, 4, 3, 13, 14, 9] (dist:7)
// -> 10: [] (dist:0)
// -> 11: [7, 5, 11] (dist:3)
// -> 12: [7, 5, 11, 12] (dist:4)
// -> 13: [7, 5, 4, 3, 13] (dist:5)
// -> 14: [7, 5, 4, 3, 13, 14] (dist:6)
// -> 15: [7, 5, 4, 3, 6, 15] (dist:6)
// -> R: [7, 5, 4, 2, R] (dist:5)
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
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
# 参考
编辑 (opens new window)
上次更新: 2022/10/18, 09:41:50