-
Notifications
You must be signed in to change notification settings - Fork 0
/
calculationFunctions.ts
55 lines (47 loc) · 1.41 KB
/
calculationFunctions.ts
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
// Reference: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
import { MapOutput } from 'src/models/map.model';
const calculateFastRouteBetweenTwoPoints = (
map: MapOutput,
start: string,
end: string,
) => {
const distances = {};
const previous = {};
let totalCost = 0;
const unvisited = new Set<string>();
for (const position in map) {
distances[position] = position === start ? 0 : Infinity;
unvisited.add(position);
}
while (unvisited.size > 0) {
let closestPosition: string = null;
for (const position of unvisited) {
if (
!closestPosition ||
distances[position] < distances[closestPosition]
) {
closestPosition = position;
}
}
if (distances[closestPosition] === Infinity) break;
if (closestPosition === end) break;
for (const neighbor in map[closestPosition]) {
const newDistance =
distances[closestPosition] + map[closestPosition][neighbor];
if (newDistance < distances[neighbor]) {
distances[neighbor] = newDistance;
previous[neighbor] = closestPosition;
}
}
unvisited.delete(closestPosition);
}
const path = [];
let endPosition = end;
while (endPosition) {
path.push(endPosition);
endPosition = previous[endPosition];
}
totalCost = distances[path[0]];
return { path: path.reverse(), cost: totalCost };
};
export { calculateFastRouteBetweenTwoPoints };