/
dijkstra.js
69 lines (67 loc) · 1.94 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
/*
* dijkstra.js
*
* Dijkstra's single source shortest path algorithm in JavaScript.
*
* Cameron McCormack <cam (at) mcc.id.au>
*
* Permission is hereby granted to use, copy, modify and distribute this
* code for any purpose, without fee.
*
* Initial version: October 21, 2004
*/
var NUMBER_NODES = d3.values(nodes).length;
var adjacencyMatrix = new Array(NUMBER_NODES);
// Initialize an adjacency matrix
for (var i = 0; i < NUMBER_NODES; i++) {
adjacencyMatrix[i] = new Array(NUMBER_NODES);
for (var j = 0; j < NUMBER_NODES; j++) {
adjacencyMatrix[i][j] = Infinity;
}
}
function shortestPath(edges, numVertices, startVertex) {
var done = new Array(numVertices);
done[startVertex] = true;
var pathLengths = new Array(numVertices);
var predecessors = new Array(numVertices);
for (var i = 0; i < numVertices; i++) {
pathLengths[i] = edges[startVertex][i];
if (edges[startVertex][i] != Infinity) {
predecessors[i] = startVertex;
}
}
pathLengths[startVertex] = 0;
for (var i = 0; i < numVertices - 1; i++) {
var closest = -1;
var closestDistance = Infinity;
for (var j = 0; j < numVertices; j++) {
if (!done[j] && pathLengths[j] < closestDistance) {
closestDistance = pathLengths[j];
closest = j;
}
}
done[closest] = true;
for (var j = 0; j < numVertices; j++) {
if (!done[j]) {
var possiblyCloserDistance = pathLengths[closest] + edges[closest][j];
if (possiblyCloserDistance < pathLengths[j]) {
pathLengths[j] = possiblyCloserDistance;
predecessors[j] = closest;
}
}
}
}
return {
"startVertex": startVertex,
"pathLengths": pathLengths,
"predecessors": predecessors
};
}
function constructPath(shortestPathInfo, endVertex) {
var path = [];
while (endVertex != shortestPathInfo.startVertex) {
path.unshift(endVertex);
endVertex = shortestPathInfo.predecessors[endVertex];
}
return path;
}