#1976

Medium

auto_awesomeGraph indegree plus topological ordering

LeetCode Problem Workspace

Number of Ways to Arrive at Destination

Find the number of ways to travel from intersection 0 to n - 1 in the shortest time, using a graph-based approach.

dynamic programming graph topological sort shortest path

Problem Statement

In a city with n intersections numbered from 0 to n - 1, there are bi-directional roads between some intersections. Each road has an associated travel time. You are provided with a 2D integer array roads, where each element represents a road between two intersections along with the time it takes to travel that road. Your goal is to calculate how many distinct ways you can travel from intersection 0 to intersection n - 1 in the shortest time possible.

Given the constraints that there is always a path between any two intersections and no more than one road between any two intersections, you must determine the number of shortest paths modulo 109 + 7. The solution requires calculating the shortest path using dynamic programming, graph indegree, and topological ordering.

Examples

Example 1

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]]

Output: 4

The shortest amount of time it takes to go from intersection 0 to intersection 6 is 7 minutes. The four ways to get there in 7 minutes are:

0 ➝ 6
0 ➝ 4 ➝ 6
0 ➝ 1 ➝ 2 ➝ 5 ➝ 6
0 ➝ 1 ➝ 3 ➝ 5 ➝ 6

Example 2

Input: n = 2, roads = [[1,0,10]]

Output: 1

There is only one way to go from intersection 0 to intersection 1, and it takes 10 minutes.

Constraints

1 <= n <= 200
n - 1 <= roads.length <= n * (n - 1) / 2
roads[i].length == 3
0 <= ui, vi <= n - 1
1 <= timei <= 109
ui != vi
There is at most one road connecting any two intersections.
You can reach any intersection from any other intersection.

Solution Approach

Shortest Path Calculation

The first step is to use a shortest path algorithm, such as Dijkstra's algorithm, to compute the minimum travel time from intersection 0 to every other intersection. After obtaining the shortest times, we can then focus on edges where dist[u] + weight = dist[v] to identify the shortest paths.

Graph Indegree and Topological Sort

With the shortest path times known, we can use topological sorting to order the graph vertices based on their dependencies. For each intersection, we check its predecessors and count the number of distinct ways to reach it using dynamic programming, adding counts from its predecessor intersections whenever a shortest path is found.

Dynamic Programming to Count Paths

We maintain a dynamic programming table to store the number of ways to reach each intersection. For each road that forms part of a shortest path, we increment the count of ways to reach the destination intersection by adding the count from the source intersection.

Complexity Analysis

Metric	Value
Time	O(N^3)
Space	O(N^2)

The time complexity of this solution is O(N^3), where N is the number of intersections, due to the use of Dijkstra’s algorithm and topological sorting. The space complexity is O(N^2) because we maintain distance and path count arrays for each intersection.

What Interviewers Usually Probe

The candidate effectively uses dynamic programming to calculate the number of shortest paths.
The candidate demonstrates understanding of graph algorithms and topological sorting.
The candidate correctly handles modular arithmetic and edge cases involving multiple shortest paths.

Common Pitfalls or Variants

Common pitfalls

Failing to handle multiple shortest paths correctly.
Incorrect use of the topological order when updating the dynamic programming table.
Not applying modular arithmetic as specified in the problem statement.

Follow-up variants

Consider a version where roads have different weights or are directed.
Implement an optimized version using BFS for unweighted graphs.
Extend the problem to calculate the number of paths in graphs with cycles.

FAQ

How do I count the number of distinct paths in this problem?

You calculate the shortest path using a graph algorithm, then use dynamic programming to count all distinct ways to reach the destination along these shortest paths.

What is the primary pattern used in the "Number of Ways to Arrive at Destination" problem?

The primary pattern involves graph indegree and topological ordering combined with dynamic programming to count the number of shortest paths.

How do I handle multiple shortest paths between intersections?

You use dynamic programming to accumulate the count of paths for each intersection as you process the roads that form part of the shortest paths.

Why do we use topological sorting in this problem?

Topological sorting is used to order the intersections so that we can process each one in a way that respects its dependencies on other intersections, ensuring we count paths correctly.

What is the time complexity of this problem?

The time complexity is O(N^3), primarily due to the use of Dijkstra’s algorithm and the processing of the graph in topological order.

terminal

Solution

Solution 1: Naive Dijkstra Algorithm

We define the following arrays:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        g = [[inf] * n for _ in range(n)]
        for u, v, t in roads:
            g[u][v] = g[v][u] = t
        g[0][0] = 0
        dist = [inf] * n
        dist[0] = 0
        f = [0] * n
        f[0] = 1
        vis = [False] * n
        for _ in range(n):
            t = -1
            for j in range(n):
                if not vis[j] and (t == -1 or dist[j] < dist[t]):
                    t = j
            vis[t] = True
            for j in range(n):
                if j == t:
                    continue
                ne = dist[t] + g[t][j]
                if dist[j] > ne:
                    dist[j] = ne
                    f[j] = f[t]
                elif dist[j] == ne:
                    f[j] += f[t]
        mod = 10**9 + 7
        return f[-1] % mod

Continue Practicing

#1786 number of restricted paths from first to last node #1916 count ways to build rooms in an ant colony #2050 parallel courses iii