You are given an undirected, weighted graph with n nodes (numbered from 0 to n-1) and a list of edges, where each edge is described as [u, v, time]. This means there is a road between node u and node v that takes time units to traverse.
Your task is to find the number of different shortest paths from node 0 (the starting point) to node n-1 (the destination), where a path's time is the sum of times of its edges. Since the answer can be very large, return it modulo 109+7.
0 to n-1.At first glance, the problem appears similar to finding the shortest path in a weighted graph, which is a classic problem solved by Dijkstra's algorithm. However, the twist here is that we are not just interested in the shortest distance, but also in counting the number of distinct shortest paths from the start to the destination.
A brute-force approach would be to enumerate all possible paths from 0 to n-1, compute their total times, and count how many have the minimum time. However, this is highly inefficient due to the exponential number of possible paths in a graph.
To optimize, we need a way to both compute the shortest times to each node and, at the same time, keep track of how many ways we can reach each node with that minimal time. This suggests a modification to Dijkstra's algorithm, where for each node we not only store the minimal time to reach it but also the count of ways to reach it in that minimal time.
We'll use a modified version of Dijkstra's algorithm to solve this problem efficiently. Here’s how:
(neighbor, time) pairs.
dist where dist[i] is the shortest time to reach node i.
ways where ways[i] is the number of distinct shortest paths to node i.
dist[0] = 0 and ways[0] = 1. All other dist values are set to infinity, and ways to 0.u with the smallest current time t.v of u with edge time time:
dist[v] > t + time (found shorter path): update dist[v] and set ways[v] = ways[u].dist[v] == t + time (found another shortest path): increment ways[v] by ways[u] (modulo 10^9+7).ways[n-1], the number of shortest paths to the destination.
This approach ensures that every time we find a new shortest path to a node, we update both the minimal time and the count of ways, efficiently and without redundant computation.
Sample Input:
n = 7,
roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]
Let's trace the process:
0 with dist[0] = 0 and ways[0] = 1.0, possible moves:
6 in 7 units1 in 2 units4 in 5 units1 next (smallest time: 2). Update dist[1] = 2, ways[1] = 1.1, reach 2 (dist[2]=5, ways[2]=1), 3 (dist[3]=5, ways[3]=1).4 (time: 5), update dist[4]=5, ways[4]=1.dist and ways as described above.ways accordingly.n-1 = 6, we find all the shortest paths and count them.
The final answer is the value of ways[n-1].
Brute-force approach:
O(M \log N), where M is the number of edges and N is the number of nodes. Each edge is processed at most once, and the priority queue operations take \log N time.
O(N + M) for the adjacency list, dist, and ways arrays.
The optimized approach is efficient and scalable for large graphs.
The problem of counting the number of shortest paths in a weighted graph is elegantly solved by augmenting Dijkstra's algorithm to keep track of both shortest distances and the number of ways to achieve those distances. By maintaining two arrays—one for minimal times and one for path counts—we efficiently compute the result in a single traversal, avoiding redundant work and ensuring scalability. This technique is a powerful example of how classic algorithms can be adapted to solve more complex counting problems.
from heapq import heappush, heappop
class Solution:
def countPaths(self, n, roads):
MOD = 10**9 + 7
from collections import defaultdict
graph = defaultdict(list)
for u, v, t in roads:
graph[u].append((v, t))
graph[v].append((u, t))
import sys
dist = [sys.maxsize] * n
ways = [0] * n
dist[0] = 0
ways[0] = 1
heap = [(0, 0)] # (time, node)
while heap:
time, u = heappop(heap)
if time > dist[u]:
continue
for v, t in graph[u]:
if dist[v] > time + t:
dist[v] = time + t
ways[v] = ways[u]
heappush(heap, (dist[v], v))
elif dist[v] == time + t:
ways[v] = (ways[v] + ways[u]) % MOD
return ways[n-1] % MOD
#include <vector>
#include <queue>
#include <climits>
using namespace std;
class Solution {
public:
int countPaths(int n, vector<vector<int>>& roads) {
const int MOD = 1e9 + 7;
vector<vector<pair<int,int>>> graph(n);
for (auto& r : roads) {
graph[r[0]].push_back({r[1], r[2]});
graph[r[1]].push_back({r[0], r[2]});
}
vector<long long> dist(n, LLONG_MAX);
vector<int> ways(n, 0);
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
dist[0] = 0;
ways[0] = 1;
pq.push({0, 0});
while (!pq.empty()) {
auto [time, u] = pq.top(); pq.pop();
if (time > dist[u]) continue;
for (auto& [v, t] : graph[u]) {
if (dist[v] > time + t) {
dist[v] = time + t;
ways[v] = ways[u];
pq.push({dist[v], v});
} else if (dist[v] == time + t) {
ways[v] = (ways[v] + ways[u]) % MOD;
}
}
}
return ways[n-1];
}
};
import java.util.*;
class Solution {
public int countPaths(int n, int[][] roads) {
int MOD = 1_000_000_007;
List<List<int[]>> graph = new ArrayList<>();
for (int i = 0; i < n; ++i) graph.add(new ArrayList<>());
for (int[] r : roads) {
graph.get(r[0]).add(new int[]{r[1], r[2]});
graph.get(r[1]).add(new int[]{r[0], r[2]});
}
long[] dist = new long[n];
Arrays.fill(dist, Long.MAX_VALUE);
int[] ways = new int[n];
PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
dist[0] = 0;
ways[0] = 1;
pq.offer(new long[]{0, 0});
while (!pq.isEmpty()) {
long[] top = pq.poll();
long time = top[0];
int u = (int)top[1];
if (time > dist[u]) continue;
for (int[] edge : graph.get(u)) {
int v = edge[0], t = edge[1];
if (dist[v] > time + t) {
dist[v] = time + t;
ways[v] = ways[u];
pq.offer(new long[]{dist[v], v});
} else if (dist[v] == time + t) {
ways[v] = (ways[v] + ways[u]) % MOD;
}
}
}
return ways[n-1];
}
}
/**
* @param {number} n
* @param {number[][]} roads
* @return {number}
*/
var countPaths = function(n, roads) {
const MOD = 1e9 + 7;
const graph = Array.from({length: n}, () => []);
for (const [u, v, t] of roads) {
graph[u].push([v, t]);
graph[v].push([u, t]);
}
const dist = Array(n).fill(Infinity);
const ways = Array(n).fill(0);
dist[0] = 0;
ways[0] = 1;
// Min-heap: [time, node]
const heap = [[0, 0]];
while (heap.length) {
heap.sort((a, b) => a[0] - b[0]);
const [time, u] = heap.shift();
if (time > dist[u]) continue;
for (const [v, t] of graph[u]) {
if (dist[v] > time + t) {
dist[v] = time + t;
ways[v] = ways[u];
heap.push([dist[v], v]);
} else if (dist[v] === time + t) {
ways[v] = (ways[v] + ways[u]) % MOD;
}
}
}
return ways[n-1] % MOD;
};