Number of Restricted Paths From First to Last Node LeetCode solution in JavaScript

1
var countRestrictedPaths = function (n, edges) {
2
  // create an adjacency list to store the neighbors with weight for each node
3
  const adjList = new Array(n + 1).fill(null).map(() => new Array(0));
4
  for (const [node1, node2, weight] of edges) {
5
    adjList[node1].push([node2, weight]);
6
    adjList[node2].push([node1, weight]);
7
  }
8

9
  // using djikstras algorithm
10
  // find the shortest path from n to each node
11
  const nodeToShortestPathDistance = {};
12
  const heap = new Heap();
13
  heap.push([n, 0]);
14
  let numNodeSeen = 0;
15
  while (numNodeSeen < n) {
16
    const [node, culmativeWeight] = heap.pop();
17
    if (nodeToShortestPathDistance.hasOwnProperty(node)) {
18
      continue;
19
    }
20
    nodeToShortestPathDistance[node] = culmativeWeight;
21
    numNodeSeen++;
22
    for (const [neighbor, edgeWeight] of adjList[node]) {
23
      if (nodeToShortestPathDistance.hasOwnProperty(neighbor)) {
24
        continue;
25
      }
26
      heap.push([neighbor, edgeWeight + culmativeWeight]);
27
    }
28
  }
29

30
  // do a DFS caching the number of paths for each node
31
  // so that we don't need to redo the number of paths again
32
  // when we visit that node through another path
33
  const nodeToNumPaths = {};
34
  const dfs = (node) => {
35
    if (node === n) return 1;
36
    if (nodeToNumPaths.hasOwnProperty(node)) {
37
      return nodeToNumPaths[node];
38
    }
39
    let count = 0;
40
    for (const [neighbor, weight] of adjList[node]) {
41
      if (
42
        nodeToShortestPathDistance[node] > nodeToShortestPathDistance[neighbor]
43
      ) {
44
        count += dfs(neighbor);
45
      }
46
    }
47
    return (nodeToNumPaths[node] = count % 1000000007);
48
  };
49
  return dfs(1);
50
};
51

52
class Heap {
53
  constructor() {
54
    this.store = [];
55
  }
56

57
  peak() {
58
    return this.store[0];
59
  }
60

61
  size() {
62
    return this.store.length;
63
  }
64

65
  pop() {
66
    if (this.store.length < 2) {
67
      return this.store.pop();
68
    }
69
    const result = this.store[0];
70
    this.store[0] = this.store.pop();
71
    this.heapifyDown(0);
72
    return result;
73
  }
74

75
  push(val) {
76
    this.store.push(val);
77
    this.heapifyUp(this.store.length - 1);
78
  }
79

80
  heapifyUp(child) {
81
    while (child) {
82
      const parent = Math.floor((child - 1) / 2);
83
      if (this.shouldSwap(child, parent)) {
84
        [this.store[child], this.store[parent]] = [
85
          this.store[parent],
86
          this.store[child],
87
        ];
88
        child = parent;
89
      } else {
90
        return child;
91
      }
92
    }
93
  }
94

95
  heapifyDown(parent) {
96
    while (true) {
97
      let [child, child2] = [1, 2]
98
        .map((x) => parent * 2 + x)
99
        .filter((x) => x < this.size());
100
      if (this.shouldSwap(child2, child)) {
101
        child = child2;
102
      }
103
      if (this.shouldSwap(child, parent)) {
104
        [this.store[child], this.store[parent]] = [
105
          this.store[parent],
106
          this.store[child],
107
        ];
108
        parent = child;
109
      } else {
110
        return parent;
111
      }
112
    }
113
  }
114

115
  shouldSwap(child, parent) {
116
    return child && this.store[child][1] < this.store[parent][1];
117
  }
118
}