-
Notifications
You must be signed in to change notification settings - Fork 0
/
dijkstra.js
81 lines (64 loc) · 1.98 KB
/
dijkstra.js
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
d3.dijkstra = function () {
var dijkstra = {}, nodes, edges, source, dispatch = d3.dispatch("start", "tick", "step", "end");
var update = function(node) {
node.links.forEach(function(link) {
var tar = link.target;
if (!tar.visited) {
var dist = current.distance + link.value;
tar.distance = Math.min(dist, tar.distance);
}
});
};
dijkstra.run = function (src) {
source = src;
var unvisited = new Heap(function(a, b) { return a.distance - b.distance });
nodes.forEach(function (d) {
if (d != src) {
d.distance = Infinity;
unvisited.push(d);
d.visited = false;
}
});
var current = src;
current.distance = 0;
function tick() {
current.visited = true;
update(current, unvisited);
if (unvisited.length == 0 || current.distance == Infinity) {
dispatch.end()
return true;
}
// We would sort the unvisited list here, but we hope that our update function does it for us.
current = unvisited.pop()
dispatch.tick();
return false;
}
d3.timer(tick);
};
dijkstra.nodes = function (_) {
if (!arguments.length)
return nodes;
else {
nodes = _;
return dijkstra;
}
};
dijkstra.update = function (_) {
if (!arguments.length)
return update;
else {
update = _;
return dijkstra;
}
};
dijkstra.source = function(_) {
if (!arguments.length)
return source;
else {
source = _;
return dijkstra;
}
};
dispatch.on("start.code", dijkstra.run);
return d3.rebind(dijkstra, dispatch, "on", "end", "start", "tick");
};