Bellman-Ford (TLE) and SPFA (AC)
Synopsis:\n\nBellman-Ford results in TLE.  SPFA is a natural progression from Bellman-Ford which only considers each next round of edge relaxations to be perfor
**Synopsis:**\n\n[Bellman-Ford](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm) results in TLE.  [SPFA](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm) is a natural progression from [Bellman-Ford](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm) which only considers each next round of edge relaxations to be performed upon the candidates which can be potentially relaxed, ie. the current candidates `cur` are formulated from the previous candidates `pre`.\n\nOnce the distances `dist` from the source node `N` have been calculated, perform DFS + BT to explore all paths from `1..N` which are strictly monotonically decreasing in distance.  Perform memoization to store the solutions to sub-problems to avoid TLE, and don\'t forget to mod the count `cnt` of these paths by `1e9 + 7`.\n\n---\n\n**Contest 231 Screenshare:**\n\n![image](https://assets.leetcode.com/users/images/1fa403ee-df57-44aa-87d0-71f469eee9bf_1615089739.5148141.png)\n\n\n---\n\n**Bellman-Ford (TLE):**\n```\nlet countRestrictedPaths = (N, E, mod = Number(1e9 + 7), cnt = 0) => {\n    let dist = Array(N + 1).fill(Infinity); // +1 for 1-based indexing, ie. the 0-th index isn\'t used\n    dist[N] = 0; // source node is N, calc dist to source by relaxing edges N - 1 times\n    let K = N - 1;\n    while (K--) { // for N - 1 iterations: relax edges u->v and v->u of weight w\n        E.forEach(([u, v, w]) => {\n            if (dist[v] > dist[u] + w) dist[v] = dist[u] + w;\n            if (dist[u] > dist[v] + w) dist[u] = dist[v] + w;\n        });\n    }\n    let adj = new Map();\n    E.forEach(([u, v, w]) => {\n        if (!adj.has(u)) adj.set(u, new Set()); adj.set(u, adj.get(u).add(v));\n        if (!adj.has(v)) adj.set(v, new Set()); adj.set(v, adj.get(v).add(u));\n    });\n    let m = new Map();\n    let go = (u = 1, path = new Set(), cnt = 0) => {\n        if (m.has(u))\n            return m.get(u);\n        if (u == N)\n            return 1;\n        path.add(u);    // forward-tracking\n        for (let v of adj.get(u))\n            if (dist[u] > dist[v] && !path.has(v))\n                cnt = (cnt + go(v, path)) % mod;\n        path.delete(u); // back-tracking\n        return m.set(u, cnt).get(u);\n    };\n    return go();\n};\n```\n\n**SPFA (AC):**\n```\nlet countRestrictedPaths = (N, E, mod = Number(1e9 + 7), cnt = 0) => {\n    let adj = new Map();\n    let key = (u, v) => `${u},${v}`;\n    let cost = new Map();\n    E.forEach(([u, v, w]) => {\n        if (!adj.has(u)) adj.set(u, new Set()); adj.set(u, adj.get(u).add(v)); cost.set(key(u, v), w);\n        if (!adj.has(v)) adj.set(v, new Set()); adj.set(v, adj.get(v).add(u)); cost.set(key(v, u), w);\n    });\n    let dist = Array(N + 1).fill(Infinity); // +1 for 1-based indexing, ie. the 0-th index isn\'t used\n    dist[N] = 0; // calculate distance to source node N by relaxing current candidate edges which are formulated based upon the previous edge relaxations\n    let cur = [N];\n    while (cur.length) {\n        let pre = [...cur]; cur = [];\n        for (let u of pre)\n            for (let v of adj.get(u))\n                if (dist[v] > dist[u] + cost.get(key(u, v)))\n                    dist[v] = dist[u] + cost.get(key(u, v)), cur.push(v);\n    }\n    let m = new Map();\n    let go = (u = 1, path = new Set(), cnt = 0) => {\n        if (m.has(u))\n            return m.get(u);\n        if (u == N)\n            return 1;\n        path.add(u);    // forward-tracking\n        for (let v of adj.get(u))\n            if (dist[u] > dist[v] && !path.has(v))\n                cnt = (cnt + go(v, path)) % mod;\n        path.delete(u); // back-tracking\n        return m.set(u, cnt).get(u);\n    };\n    return go();\n};\n```
[]