-
Notifications
You must be signed in to change notification settings - Fork 10
/
ShortestPath.html
87 lines (79 loc) · 2.11 KB
/
ShortestPath.html
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
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Title</title>
</head>
<body>
<script>
// 无向图最短路径算法
class ShortestPath {
constructor(arr) {
this.visited = new Array(arr.length).fill(false);
this.from = new Array(arr.length).fill(-1);
this.ord = new Array(arr.length).fill(-1);
this.graph = arr;
this.queue = [];
}
pathStart(s) {
this.queue.push(s);
this.ord[s] = 0;
this.visited[s] = true;
while (this.queue.length) {
let v = this.queue.shift();
for (let i = 0; i < this.graph[v].length; i++) {
let temp = this.graph[v][i];
if (!this.visited[temp]) {
this.queue.push(temp);
this.visited[temp] = true;
this.from[temp] = v;
this.ord[temp] = this.ord[v] + 1;
}
}
}
console.log(this.ord);
return this
}
find(w, vec) {
let stack = [],
p = w;
while (p !== -1) {
stack.push(p);
p = this.from[p];
}
let temp;
while (stack.length) {
temp = stack.pop();
vec.push(temp);
}
}
showPath(w) {
let vector = [],
path = '';
this.find(w, vector)
for (let i = 0; i < vector.length; i++) {
if (i === vector.length - 1) {
path += vector[i]
} else {
path += `${vector[i]} -> `
}
}
console.log(path)
}
length(w) {
return this.ord[w];
}
}
let graph = [
[1, 2, 5, 6],
[0],
[0],
[4, 5],
[3, 5, 6],
[0, 3, 4],
[0, 4]
];
new ShortestPath(graph).pathStart(0).showPath(3)
</script>
</body>
</html>