给定一个包含从 0 到 V-1 的 V 顶点的无向加权图，表示为邻接列表 adj[][]，其中每个 adj[u] 包含对 [v， t]，表明节点 u 和 v 之间存在一条边，使得从 t 到达 v 或 v 到达 u 需要时间。
找出从第0节点到第（V-1）节点在最短时间内到达（V-1）节点的不同路径数量。
示例：
输入：形容词[][] = [[[1， 2]， [3， 5]，[0， 2]， [2， 3]， [3， 3]，
[1， 3]， [3， 4]，[0， 5]， [1， 3]， [2， 4]]]
输出：2
解释：从0到3的最短路径存在两条路径：0 - > 3和0 -> 1 - > 3，每条路径成本为5。
输入：形容词[][] =[[[2， 3]， [4， 2]， [5， 7]，
[[4， 1]， [5， 4]， [[0， 3]， [3， 1]， [5， 5]]，
[2， 1]， [5， 3]，[[0， 2]， [1， 1]， [5， 5]]，
[[0， 7]， [1， 4]， [2， 5]， [3， 3]， [4， 5]]
输出：4
说明：从0到5的最短路径为-
0 -> 5 （7）
0 -> 4 -> 5 （2+ 5 = 7）
0 -> 4 -> 1 -> 5（2 + 1 + 4 = 7）
0 -> 2 -> 3 -> 5 （3 + 1 + 3 = 7）
修剪的DFS制作
我们从节点0启动DFS，探索通往目的地n-1的所有可能路径。在探索过程中，我们会追踪到目前为止所用的总时间。如果这段时间超过当前的最佳（最短）时间，我们就停止探索那条路径，因为我们已经知道有一条更快的路径通过其他路径存在。如果到达目的地，我们会检查这条路径是否比之前所有路径都快;如果是，我们更新最短时间，并将方法计数重置为1。如果时间匹配当前最短时间，我们只需增加计数。
在DFS中，我们会将节点标记为已访问，以避免在同一路径中重复访问，回溯时取消标记，以便其他路径能重复使用该节点。通过这种方式，我们系统地尝试所有有效路径，修剪那些注定会更糟的路径，最后统计有多少条不同路径达到了最小可能的时间。
function dfs(node, currentTime, adj, vis, V, shortest, ways) { // prune: no need to go further if (currentTime > shortest[0]) return; if (node === V - 1) { // if time to reach the node is new minimum // change the number of ways to 1(for current path) if (currentTime < shortest[0]) { shortest[0] = currentTime; ways[0] = 1; } // increment the number of ways to // reach the node in shortest time else if (currentTime === shortest[0]) { ways[0]++; } return; } vis[node] = 1; for (let p of adj[node]) { let next = p[0]; let wt = p[1]; if (vis[next] === 0) { dfs(next, currentTime + wt, adj, vis, V, shortest, ways); } } // backtracking and marking // node as unvisited vis[node] = 0; } function countPaths(adj) { let V = adj.length; let vis = Array(V).fill(0); // to store the shortest time // needed to reach node V-1 from 0 let shortest = [Number.MAX_SAFE_INTEGER]; // number of ways to reach // node V-1 in shortest time let ways = [0]; dfs(0, 0, adj, vis, V, shortest, ways); return ways[0]; } function addEdge(adj, u, v, wt) { adj[u].push([v, wt]); adj[v].push([u, wt]); } // Driver code let V = 4; let adj = Array.from({ length: V }, () => []); addEdge(adj, 0, 1, 2); addEdge(adj, 0, 3, 5); addEdge(adj, 1, 2, 3); addEdge(adj, 1, 3, 3); addEdge(adj, 2, 3, 4); console.log(countPaths(adj));输出
2
时间复杂度：O（KV其中 K 是图中顶点的平均分支因子，V 是图中顶点的数量。
空间复杂度：O（V），其中V是图中的顶点数。
[预期方法]使用迪克斯特拉算法 - O（V+ E log E） 时间和 O（V+E） 空间
由于我们需要找到从源到目的的不同最短路径，且图中包含正边权重，我们可以使用迪克斯特拉算法。这里，我们使用Dijkstra算法跟踪每个节点的最短时间和在最短时间内到达该节点的方式数量。我们维护一个 minTime[] 数组，表示到达每个节点的最佳时间，以及一个 paths[] 数组，表示通往该节点的最短路径数量。当我们放松边时，如果找到一个严格更好的时间，我们会同时更新时间和路径计数。如果我们找到相等时间，则将当前节点的路径数相加。到最后，路径[V-1]给出了通往目的地的最短路径总数。
function countPaths(adj) { let V = adj.length; // min time to reach a node from src(0) let minTime = Array(V).fill(Number.MAX_SAFE_INTEGER); // number of ways to reach a node // from src(0) with minimum cost let paths = Array(V).fill(0); minTime[0] = 0; paths[0] = 1; // sort nodes by time taken to reach // them from src in ascending order let pq = [[0, 0]]; // [node, time] while (pq.length) { pq.sort((a, b) => a[0] - b[0]); let [currentTime, node] = pq.shift(); if (currentTime > minTime[node]) continue; for (let [nextNode, nextTime] of adj[node]) { let newTime = nextTime + currentTime; // if newTime is less than stored value // then update paths and time if (newTime < minTime[nextNode]) { minTime[nextNode] = newTime; paths[nextNode] = paths[node]; pq.push([newTime, nextNode]); } else if (newTime === minTime[nextNode]) { // increment the count of // paths if time is same paths[nextNode] = (paths[nextNode] + paths[node]); } } } // return number of paths to reach // dest from src in min time return paths[V - 1]; } function addEdge(adj, u, v, wt) { adj[u].push([v, wt]); adj[v].push([u, wt]); } // Driver code let V = 4; let adj = Array.from({ length: V}, () => []); addEdge(adj, 0, 1, 2); addEdge(adj, 0, 3, 5); addEdge(adj, 1, 2, 3); addEdge(adj, 1, 3, 3); addEdge(adj, 2, 3, 4); console.log(countPaths(adj));输出
2
编程资源 https://pan.quark.cn/s/7f7c83756948 更多资源 https://pan.quark.cn/s/bda57957c548
