-
Notifications
You must be signed in to change notification settings - Fork 0
/
script.js
68 lines (52 loc) 路 1.9 KB
/
script.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
const shortestPathTo = [7, 37, 59, 82, 99, 115, 133, 165, 188, 197];
const startVertice = 1;
function dijkstra(adjacencies, cost, from, to) {
let n = adjacencies.length;
const dist = new Array(n).fill(Infinity);
dist[from] = 0;
const dist2 = [...dist];
while (n) {
let u = dist2.indexOf(Math.min(...dist2));
dist2[u] = Infinity;
for (let i = 0; i < adjacencies[u].length; i++) {
let v = adjacencies[u][i];
if (dist[v] > dist[u] + cost[u][i]) {
dist[v] = dist[u] + cost[u][i];
dist2[v] = dist[v];
}
}
n--;
}
return dist[to] === Infinity ? -1 : dist[to];
}
function getData(taskFile) {
const fs = require('fs');
const data = fs.readFileSync(taskFile, 'utf8');
const adjacencies = [['empty']], // since 1-based counting
cost = [['empty']]; // since 1-based counting
const dataArr = data.split('\n');
for (let line of dataArr) {
if (line !== '') {
const lineArr = line.trim().split('\t');
const from = parseInt(lineArr.shift());
adjacencies.push([]);
cost.push([]);
for (let verticeData of lineArr) {
const [vertice, weight] = verticeData.split(',').map(Number);
adjacencies[from].push(vertice);
cost[from].push(weight);
}
}
}
return [adjacencies, cost];
}
function solve(shortestPathTo, startVertice, adjacencies, cost) {
const result = [];
for (let finishVertice of shortestPathTo) {
const path = dijkstra(adjacencies, cost, startVertice, finishVertice);
result.push(path);
}
return result.join(',');
}
const [adjacencies, cost] = getData('dijkstraData.txt');
console.log(solve(shortestPathTo, startVertice, adjacencies, cost)); // Answer: 2599,2610,2947,2052,2367,2399,2029,2442,2505,3068