-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDijkstra's Algorithm.js
More file actions
87 lines (75 loc) · 2.25 KB
/
Dijkstra's Algorithm.js
File metadata and controls
87 lines (75 loc) · 2.25 KB
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
Thanks to Andreas Hultgren for pointers
//implement heap
function PriorityQueue() {
this.dataStore = [];
this.enqueue = enqueue;
this.dequeue = dequeue;
this.isEmpty = isEmpty;
}
function sorter(a, b) {
return a.priority > b.priority;
}
function enqueue(priority, data) {
this.dataStore.push({priority: priority, data: data});
this.dataStore.sort(sorter);
}
function dequeue() {
return this.dataStore.shift().data;
}
function isEmpty() {
return this.dataStore.length < 1;
}
//graph constructor
function Graph() {
this.vertices = [];
this.addVertex = addVertex;
this.shortestPath = shortestPath;
}
function addVertex(name, edges) {
this.vertices[name] = edges;
}
function shortestPath(start, finish) {
var priorityQueue = new PriorityQueue();
var distances = {}, previous = {}, path = [];
for (var vertex in this.vertices) {
if (vertex == start) {
distances[vertex] = 0;
priorityQueue.enqueue(0, vertex);
}
else {
distances[vertex] = Infinity;
priorityQueue.enqueue(Infinity, vertex);
}
previous[vertex] = null;
}
while (!priorityQueue.isEmpty()) {
var smallest = priorityQueue.dequeue();
if (smallest == finish) {
while (previous[smallest]) {
path.push(smallest);
smallest = previous[smallest];
}
break;
}
if (!smallest || distances[smallest] == Infinity) {
continue;
}
for (var neighbor in this.vertices[smallest]) {
var alt = distances[smallest] + this.vertices[smallest][neighbor];
if (alt < distances[neighbor]) {
distances[neighbor] = alt;
previous[neighbor] = smallest;
}
priorityQueue.enqueue(alt, neighbor);
}
}
return path;
}
var graphite = new Graph();
graphite.addVertex('A', {B: 7, C: 9, D: 14});
graphite.addVertex('B', {A: 7, C: 10, E: 15});
graphite.addVertex('C', {A: 9, B: 10, D: 2, E: 11});
graphite.addVertex('D', {A: 14, C: 2, F: 9});
graphite.addVertex('E', {B: 15, C: 11, F: 6});
graphite.addVertex('F', {D: 9, E: 6});
console.log(graphite.shortestPath('A', 'F').concat('A').reverse());