Problem Description

You are given a city with n intersections numbered from 0 to n - 1. These intersections are connected by bi-directional roads. The road network is designed such that:

• You can reach any intersection from any other intersection
• There is at most one direct road between any two intersections

The input provides:

• An integer n representing the number of intersections
• A 2D array roads where each element roads[i] = [ui, vi, timei] indicates there is a road between intersection ui and intersection vi that takes timei minutes to travel

Your task is to find the number of different ways to travel from intersection 0 to intersection n - 1 using the shortest possible time.

Since there might be multiple paths that all take the minimum time to reach the destination, you need to count all such paths. The answer should be returned modulo 10^9 + 7 as it could be very large.

For example, if the shortest time to reach from intersection 0 to intersection n - 1 is 10 minutes, and there are 3 different paths that all take exactly 10 minutes, then the answer would be 3.

Intuition

The problem asks for two things: finding the shortest path and counting how many ways we can achieve that shortest path. This naturally points us toward Dijkstra's algorithm, which finds shortest paths in weighted graphs.

The key insight is that while finding the shortest distances to each intersection, we can simultaneously track the number of ways to reach each intersection with that shortest distance.

Think of it this way: when we're exploring the graph and find a path to intersection j through intersection t, two scenarios can occur:

1. We found a shorter path: If the path through t gives us a distance of dist[t] + g[t][j] that is less than the current known shortest distance dist[j], then we've discovered a better route. In this case, we update dist[j] to this new shorter distance and set the number of ways to reach j equal to the number of ways to reach t (since all shortest paths to j must now go through t).

2. We found an equally short path: If the path through t gives us exactly the same distance as the current shortest distance to j, then we've found an alternative shortest path. We don't update the distance, but we add the number of ways to reach t to the number of ways to reach j, because we can use any of the paths to t and then continue to j.

By maintaining an array f where f[i] represents the number of shortest paths from the starting point to intersection i, we can build up the count incrementally. We start with f[0] = 1 (there's exactly one way to be at the starting point - by starting there), and as we process each intersection using Dijkstra's algorithm, we update the counts based on the two scenarios above.

The algorithm ensures that when we process an intersection t, we've already found the shortest distance to it and counted all possible shortest paths to it. This way, when we use t to update other intersections, the count f[t] is final and accurate.

Learn more about Graph, Topological Sort, Dynamic Programming and Shortest Path patterns.

Solution Approach

The solution implements the naive Dijkstra algorithm with path counting. Let's walk through the implementation step by step:

1. Initialize the Graph and Data Structures

First, we create an adjacency matrix g where g[i][j] represents the travel time between intersections i and j:

• Initialize all values to infinity (inf) to indicate no direct connection
• Set g[0][0] = 0 (distance from start to itself is 0)
• For each road [u, v, t], set g[u][v] = g[v][u] = t (bidirectional roads)

Then we initialize three arrays:

• dist[i]: shortest distance from intersection 0 to intersection i, initially all infinity except dist[0] = 0
• f[i]: number of shortest paths from intersection 0 to intersection i, initially all 0 except f[0] = 1
• vis[i]: whether intersection i has been visited, initially all False

2. Dijkstra's Algorithm with Path Counting

The algorithm runs for n iterations, and in each iteration:

a) Find the unvisited intersection with minimum distance:

t = -1
for j in range(n):
    if not vis[j] and (t == -1 or dist[j] < dist[t]):
        t = j

This finds the unvisited intersection t that has the smallest distance from the start.

b) Mark this intersection as visited:

vis[t] = True

c) Update distances and path counts for neighbors: For each intersection j that hasn't been processed yet:

ne = dist[t] + g[t][j]  # new distance through t
if dist[j] > ne:
    dist[j] = ne
    f[j] = f[t]  # All shortest paths to j now go through t
elif dist[j] == ne:
    f[j] += f[t]  # Found additional shortest paths through t

The key logic here:

• If we find a shorter path to j through t, we update dist[j] and set f[j] = f[t] because all previous paths are no longer shortest
• If we find an equally short path to j through t, we add f[t] to f[j] because we've found additional ways to reach j in the shortest time

3. Return the Result

After processing all intersections, f[n-1] contains the number of shortest paths from intersection 0 to intersection n-1. We return this value modulo 10^9 + 7:

return f[-1] % mod

The time complexity is O(n²) due to the naive implementation of Dijkstra's algorithm, where we scan all vertices to find the minimum in each iteration. The space complexity is O(n²) for storing the adjacency matrix.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Example: We have 4 intersections (n = 4) with the following roads:

• Road from 0 to 1: 2 minutes
• Road from 0 to 2: 5 minutes
• Road from 1 to 2: 1 minute
• Road from 1 to 3: 4 minutes
• Road from 2 to 3: 1 minute

Our goal is to find the number of shortest paths from intersection 0 to intersection 3.

Step 1: Initialize

• Create adjacency matrix g with road times
• dist = [0, inf, inf, inf] (shortest distances)
• f = [1, 0, 0, 0] (number of shortest paths)
• vis = [False, False, False, False] (visited status)

Iteration 1:

• Find unvisited node with minimum distance: node 0 (dist=0)
• Mark node 0 as visited: vis[0] = True
• Update neighbors:
  • Node 1: dist[1] = 0 + 2 = 2, f[1] = 1 (found first path to node 1)
  • Node 2: dist[2] = 0 + 5 = 5, f[2] = 1 (found first path to node 2)
• State: dist = [0, 2, 5, inf], f = [1, 1, 1, 0]

Iteration 2:

• Find unvisited node with minimum distance: node 1 (dist=2)
• Mark node 1 as visited: vis[1] = True
• Update neighbors:
  • Node 2: ne = 2 + 1 = 3 < 5, so dist[2] = 3, f[2] = 1 (found shorter path through node 1)
  • Node 3: dist[3] = 2 + 4 = 6, f[3] = 1 (found first path to node 3)
• State: dist = [0, 2, 3, 6], f = [1, 1, 1, 1]

Iteration 3:

• Find unvisited node with minimum distance: node 2 (dist=3)
• Mark node 2 as visited: vis[2] = True
• Update neighbors:
  • Node 0: Already visited, skip
  • Node 1: Already visited, skip
  • Node 3: ne = 3 + 1 = 4 < 6, so dist[3] = 4, f[3] = 1 (found shorter path through node 2)
• State: dist = [0, 2, 3, 4], f = [1, 1, 1, 1]

Iteration 4:

• Find unvisited node with minimum distance: node 3 (dist=4)
• Mark node 3 as visited: vis[3] = True
• All nodes visited, algorithm complete

Result: The shortest path from 0 to 3 takes 4 minutes, and there is 1 way to achieve this shortest time (path: 0→1→2→3).

Now let's modify the example to show multiple shortest paths. If we add a direct road from 0 to 3 with time 4:

After running the algorithm with this additional road:

• When we process node 0, we'd set dist[3] = 4, f[3] = 1
• When we process node 2 (with dist=3), we'd find ne = 3 + 1 = 4 == dist[3]
• Since distances are equal, we'd update: f[3] = f[3] + f[2] = 1 + 1 = 2

Result: There would be 2 shortest paths from 0 to 3, both taking 4 minutes:

1. Direct path: 0→3
2. Path through nodes: 0→1→2→3

The algorithm correctly counts both paths by accumulating the path counts when finding equal-distance routes.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n^2)

The algorithm implements Dijkstra's shortest path algorithm with path counting. The main time complexity comes from:

• The outer loop runs n iterations
• In each iteration:
  • Finding the minimum unvisited node takes O(n) time (scanning through all n nodes)
  • Updating distances to all neighbors takes O(n) time (checking all n possible connections)
• Total: n × (O(n) + O(n)) = O(n^2)

Space Complexity: O(n^2)

The space usage includes:

• Adjacency matrix g: n × n array storing edge weights = O(n^2)
• Distance array dist: stores shortest distance to each node = O(n)
• Path count array f: stores number of shortest paths to each node = O(n)
• Visited array vis: tracks processed nodes = O(n)
• Total: O(n^2) + O(n) + O(n) + O(n) = O(n^2)

The quadratic space complexity is dominated by the adjacency matrix representation of the graph.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Apply Modulo During Path Count Updates

The most critical pitfall in this solution is only applying the modulo operation at the very end when returning the result. When dealing with path counting problems where the answer can be very large, intermediate calculations can cause integer overflow even in Python (though Python handles big integers automatically, it's inefficient).

The Problem:

elif distances[neighbor] == new_distance:
    # Found another shortest path to neighbor
    path_counts[neighbor] += path_counts[current_node]  # Can grow very large!

The Solution: Apply modulo during the accumulation to keep numbers manageable:

MOD = 10**9 + 7
# ... in the update logic:
elif distances[neighbor] == new_distance:
    path_counts[neighbor] = (path_counts[neighbor] + path_counts[current_node]) % MOD

2. Incorrect Adjacency Matrix Initialization

Another common mistake is incorrectly initializing the diagonal of the adjacency matrix. The code sets adjacency_matrix[0][0] = 0, but it should set all diagonal elements to 0:

The Problem:

adjacency_matrix[0][0] = 0  # Only sets distance from node 0 to itself

The Solution:

for i in range(n):
    adjacency_matrix[i][i] = 0  # Distance from any node to itself is 0

3. Not Handling Edge Cases

The solution doesn't explicitly handle edge cases like:

• When n = 1 (start and destination are the same)
• When there's no path from node 0 to node n-1 (though the problem guarantees connectivity)

The Solution: Add edge case handling:

if n == 1:
    return 1  # Only one way when start equals destination

# After Dijkstra's algorithm:
if distances[n-1] == float('inf'):
    return 0  # No path exists

4. Inefficient Node Selection in Dijkstra's

The current implementation uses O(n) time to find the minimum distance node in each iteration, leading to O(n²) overall complexity. For sparse graphs, using a priority queue would be more efficient.

The Solution using heapq:

import heapq

def countPaths(self, n: int, roads: List[List[int]]) -> int:
    MOD = 10**9 + 7
  
    # Build adjacency list instead of matrix
    graph = [[] for _ in range(n)]
    for u, v, time in roads:
        graph[u].append((v, time))
        graph[v].append((u, time))
  
    distances = [float('inf')] * n
    distances[0] = 0
    path_counts = [0] * n
    path_counts[0] = 1
  
    # Priority queue: (distance, node)
    pq = [(0, 0)]
  
    while pq:
        curr_dist, node = heapq.heappop(pq)
      
        if curr_dist > distances[node]:
            continue
      
        for neighbor, time in graph[node]:
            new_dist = curr_dist + time
          
            if distances[neighbor] > new_dist:
                distances[neighbor] = new_dist
                path_counts[neighbor] = path_counts[node]
                heapq.heappush(pq, (new_dist, neighbor))
            elif distances[neighbor] == new_dist:
                path_counts[neighbor] = (path_counts[neighbor] + path_counts[node]) % MOD
  
    return path_counts[n-1] % MOD

This optimized version runs in O((E + V) log V) time complexity, which is much better for sparse graphs.