LeetCode 1976 - Number of Ways to Arrive at Destination

This problem gives us a weighted, undirected graph. Each intersection is a node, and each road is an edge with a travel time. We start at intersection 0 and want to reach intersection n - 1. The important detail is that we are not simply looking for the shortest distance.

leetcodemediumdynamic-programminggraph-theorytopological-sortshortest-path

LeetCode Problem 1976

Difficulty: 🟡 Medium
Topics: Dynamic Programming, Graph Theory, Topological Sort, Shortest Path

Solution

Problem Understanding

This problem gives us a weighted, undirected graph. Each intersection is a node, and each road is an edge with a travel time. We start at intersection 0 and want to reach intersection n - 1.

The important detail is that we are not simply looking for the shortest distance. We must count how many distinct paths achieve that minimum travel time.

For example, suppose the shortest travel time from node 0 to node 6 is 7. There may be several different routes whose total edge weights add up to 7. The task is to count all such shortest paths.

The graph is guaranteed to be connected, meaning every node can be reached from every other node. Roads are bi directional, so if there is a road from u to v, we can also travel from v to u with the same cost.

The constraints are important:

  • n <= 200
  • Edge weights can be very large, up to 10^9
  • The graph may be dense, with up to n * (n - 1) / 2 edges

Because edge weights are positive, this strongly suggests using Dijkstra's algorithm for shortest paths.

The tricky part is counting how many shortest paths exist while computing the minimum distance.

Several edge cases are important:

  • Multiple shortest paths may lead to the same node.
  • Very large edge weights require careful handling of integer overflow in some languages.
  • The answer may become large, so we must return it modulo 10^9 + 7.
  • There may be a direct edge from source to destination, but indirect paths with the same total cost may also exist.
  • Since the graph is connected, we never need to handle unreachable nodes.

Approaches

Brute Force Approach

A brute force solution would attempt to enumerate every possible path from node 0 to node n - 1. For each path, we would compute its total travel time and compare it against the current shortest distance.

This approach is correct because eventually every valid path is explored. After exploring all paths, we can determine:

  1. The minimum total travel time.
  2. The number of paths achieving that minimum.

However, this approach is completely impractical.

A graph can contain exponentially many paths. Even with only 200 nodes, the number of simple paths can become enormous. A DFS backtracking solution would quickly exceed time limits.

Additionally, because the graph contains cycles, we would need extra bookkeeping to avoid infinite recursion.

Optimal Approach

The key insight is that this is fundamentally a shortest path problem with positive edge weights, which makes Dijkstra's algorithm ideal.

Normally, Dijkstra computes only the minimum distance to every node. We extend it slightly so that it also tracks the number of shortest ways to reach each node.

We maintain two arrays:

  • dist[i] = shortest known distance from node 0 to node i
  • ways[i] = number of shortest paths that achieve dist[i]

While relaxing edges during Dijkstra:

  • If we find a strictly shorter path to a node, we update its distance and replace its path count.
  • If we find another path with the exact same shortest distance, we add the number of ways from the current node.

Because Dijkstra processes nodes in non decreasing distance order, every shortest path contribution is accumulated correctly.

Approach Time Complexity Space Complexity Notes
Brute Force Exponential O(n) Explores all possible paths
Optimal O((V + E) log V) O(V + E) Dijkstra with path counting

Algorithm Walkthrough

  1. Build an adjacency list for the graph.

Since the graph is undirected, every road [u, v, time] is added in both directions. The adjacency list allows efficient traversal of neighbors. 2. Initialize the shortest distance array.

Create a dist array where every value starts as infinity. Set dist[0] = 0 because the distance from the source to itself is zero. 3. Initialize the path counting array.

Create a ways array initialized to zero. Set ways[0] = 1 because there is exactly one way to stay at the starting node. 4. Create a priority queue.

Use a min heap storing pairs (distance, node). Start by pushing (0, 0).

The heap ensures we always process the node with the currently smallest known distance. 5. Process nodes using Dijkstra's algorithm.

Repeatedly pop the smallest distance entry from the heap.

If the popped distance is greater than the stored shortest distance, skip it because it represents an outdated heap entry. 6. Relax all neighboring edges.

For each neighbor:

  • Compute new_distance = current_distance + edge_weight.

  • If new_distance < dist[neighbor]:

  • Update dist[neighbor]

  • Set ways[neighbor] = ways[current_node]

  • Push the updated state into the heap

  • Else if new_distance == dist[neighbor]:

  • Add the current number of ways:

ways[neighbor] += ways[current_node]

  • Apply modulo 10^9 + 7
  1. Continue until the heap is empty.

At the end, ways[n - 1] contains the number of shortest paths to the destination.

Why it works

Dijkstra's algorithm guarantees that when a node is processed with its minimum distance, that distance is final because all edge weights are positive.

The ways array maintains the invariant that ways[i] always stores the number of shortest paths achieving dist[i].

Whenever we discover:

  • A strictly better distance, old paths are irrelevant and replaced.
  • An equally short distance, we have found additional shortest paths and add them.

Thus, after processing the entire graph, the destination node contains the correct count of shortest paths.

Python Solution

from typing import List
import heapq

class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        MOD = 10**9 + 7

        # Build adjacency list
        graph = [[] for _ in range(n)]

        for u, v, time in roads:
            graph[u].append((v, time))
            graph[v].append((u, time))

        # Shortest distance array
        dist = [float('inf')] * n
        dist[0] = 0

        # Number of shortest ways
        ways = [0] * n
        ways[0] = 1

        # Min heap: (distance, node)
        heap = [(0, 0)]

        while heap:
            current_dist, node = heapq.heappop(heap)

            # Skip outdated entries
            if current_dist > dist[node]:
                continue

            for neighbor, weight in graph[node]:
                new_dist = current_dist + weight

                # Found shorter path
                if new_dist < dist[neighbor]:
                    dist[neighbor] = new_dist
                    ways[neighbor] = ways[node]

                    heapq.heappush(heap, (new_dist, neighbor))

                # Found another shortest path
                elif new_dist == dist[neighbor]:
                    ways[neighbor] = (
                        ways[neighbor] + ways[node]
                    ) % MOD

        return ways[n - 1]

The implementation begins by constructing an adjacency list because graphs with variable numbers of neighbors are efficiently represented this way.

The dist array tracks the minimum known distance to each node. Initially every value is infinity except the source.

The ways array stores how many shortest paths exist for each node. Initially only node 0 has one valid path.

The priority queue drives Dijkstra's algorithm. Each heap entry contains the current shortest known distance paired with a node.

Inside the main loop, outdated heap entries are ignored. This happens because a node may be inserted multiple times before its final shortest distance is settled.

For each neighbor, we compute the potential new distance.

If the new distance is smaller, we replace both the shortest distance and the path count because this route is strictly better.

If the new distance equals the existing shortest distance, we accumulate additional shortest paths.

Finally, we return the number of shortest paths to node n - 1.

Go Solution

package main

import (
	"container/heap"
)

const MOD int = 1e9 + 7

type Pair struct {
	node int
	dist int64
}

type PriorityQueue []Pair

func (pq PriorityQueue) Len() int {
	return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].dist < pq[j].dist
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
	*pq = append(*pq, x.(Pair))
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)

	item := old[n-1]
	*pq = old[:n-1]

	return item
}

func countPaths(n int, roads [][]int) int {
	graph := make([][][2]int, n)

	for _, road := range roads {
		u, v, t := road[0], road[1], road[2]

		graph[u] = append(graph[u], [2]int{v, t})
		graph[v] = append(graph[v], [2]int{u, t})
	}

	dist := make([]int64, n)
	ways := make([]int, n)

	const INF int64 = 1<<62

	for i := 0; i < n; i++ {
		dist[i] = INF
	}

	dist[0] = 0
	ways[0] = 1

	pq := &PriorityQueue{}
	heap.Init(pq)

	heap.Push(pq, Pair{node: 0, dist: 0})

	for pq.Len() > 0 {
		current := heap.Pop(pq).(Pair)

		node := current.node
		currentDist := current.dist

		if currentDist > dist[node] {
			continue
		}

		for _, edge := range graph[node] {
			neighbor := edge[0]
			weight := int64(edge[1])

			newDist := currentDist + weight

			if newDist < dist[neighbor] {
				dist[neighbor] = newDist
				ways[neighbor] = ways[node]

				heap.Push(pq, Pair{
					node: neighbor,
					dist: newDist,
				})

			} else if newDist == dist[neighbor] {
				ways[neighbor] = (ways[neighbor] + ways[node]) % MOD
			}
		}
	}

	return ways[n-1]
}

The Go implementation follows the same algorithmic structure as the Python solution, but several language specific details are important.

Go's container/heap package requires implementing the heap interface manually, including Len, Less, Swap, Push, and Pop.

Distances are stored as int64 instead of int because edge weights can become very large when summed across multiple roads. Using int64 avoids overflow.

The adjacency list uses slices of fixed size arrays [2]int to store neighbor and weight pairs efficiently.

Unlike Python's dynamic integers, Go integers have fixed width, so careful type conversion is necessary when combining distances and weights.

Worked Examples

Example 1

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

Initial state:

Node dist ways
0 0 1
1 inf 0
2 inf 0
3 inf 0
4 inf 0
5 inf 0
6 inf 0

Heap:

Heap
(0,0)

Step 1, process node 0

Neighbors:

  • 0 -> 6 with cost 7
  • 0 -> 1 with cost 2
  • 0 -> 4 with cost 5

Updated state:

Node dist ways
0 0 1
1 2 1
2 inf 0
3 inf 0
4 5 1
5 inf 0
6 7 1

Heap:

Heap
(2,1), (5,4), (7,6)

Step 2, process node 1

Neighbors:

  • 1 -> 2, new distance = 5
  • 1 -> 3, new distance = 5

Updated state:

Node dist ways
0 0 1
1 2 1
2 5 1
3 5 1
4 5 1
5 inf 0
6 7 1

Step 3, process nodes 2, 3, and 4

From node 2:

  • Reach node 5 with distance 6

From node 3:

  • Reach node 5 also with distance 6
  • Add another shortest path

From node 4:

  • Reach node 6 with distance 7
  • Add another shortest path

Updated state:

Node dist ways
0 0 1
1 2 1
2 5 1
3 5 1
4 5 1
5 6 2
6 7 2

Step 4, process node 5

From node 5:

  • Reach node 6 with distance 7
  • Add two more shortest paths

Final state:

Node dist ways
0 0 1
1 2 1
2 5 1
3 5 1
4 5 1
5 6 2
6 7 4

Answer:

4

Example 2

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

Initial state:

Node dist ways
0 0 1
1 inf 0

Process node 0:

  • Reach node 1 with distance 10

Final state:

Node dist ways
0 0 1
1 10 1

Answer:

1

Complexity Analysis

Measure Complexity Explanation
Time O((V + E) log V) Each edge relaxation may push into the heap
Space O(V + E) Adjacency list, heap, distance array, and ways array

The adjacency list stores every edge twice because the graph is undirected, giving O(E) space usage.

Dijkstra's algorithm processes each edge relaxation with heap operations that cost O(log V). Since there are E edges, total time complexity becomes O((V + E) log V).

Because n <= 200, this solution easily fits within the constraints.

Test Cases

from typing import List

class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        import heapq

        MOD = 10**9 + 7

        graph = [[] for _ in range(n)]

        for u, v, t in roads:
            graph[u].append((v, t))
            graph[v].append((u, t))

        dist = [float('inf')] * n
        ways = [0] * n

        dist[0] = 0
        ways[0] = 1

        heap = [(0, 0)]

        while heap:
            current_dist, node = heapq.heappop(heap)

            if current_dist > dist[node]:
                continue

            for neighbor, weight in graph[node]:
                new_dist = current_dist + weight

                if new_dist < dist[neighbor]:
                    dist[neighbor] = new_dist
                    ways[neighbor] = ways[node]

                    heapq.heappush(heap, (new_dist, neighbor))

                elif new_dist == dist[neighbor]:
                    ways[neighbor] = (
                        ways[neighbor] + ways[node]
                    ) % MOD

        return ways[n - 1]

sol = Solution()

# Example 1
assert sol.countPaths(
    7,
    [
        [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]
    ]
) == 4  # multiple shortest paths

# Example 2
assert sol.countPaths(
    2,
    [[1,0,10]]
) == 1  # single direct edge

# Two equal shortest paths
assert sol.countPaths(
    4,
    [
        [0,1,1],
        [1,3,1],
        [0,2,1],
        [2,3,1]
    ]
) == 2  # two shortest routes

# Only one shortest path
assert sol.countPaths(
    4,
    [
        [0,1,1],
        [1,2,1],
        [2,3,1],
        [0,3,10]
    ]
) == 1  # indirect path is uniquely shortest

# Dense graph with many shortest paths
assert sol.countPaths(
    5,
    [
        [0,1,1],
        [0,2,1],
        [1,3,1],
        [2,3,1],
        [3,4,1],
        [1,4,2],
        [2,4,2]
    ]
) == 4  # several equal shortest paths

# Large weights
assert sol.countPaths(
    3,
    [
        [0,1,10**9],
        [1,2,10**9],
        [0,2,2 * 10**9]
    ]
) == 2  # verifies large integer handling

# Minimal graph
assert sol.countPaths(
    2,
    [
        [0,1,1]
    ]
) == 1  # smallest connected graph
Test Why
Example 1 Validates multiple shortest paths
Example 2 Validates simplest connected graph
Two equal shortest paths Ensures path counting logic works
Only one shortest path Verifies longer alternatives are ignored
Dense graph Tests many competing shortest routes
Large weights Ensures no overflow issues
Minimal graph Tests smallest valid input

Edge Cases

One important edge case occurs when multiple different routes produce exactly the same shortest distance. A naive Dijkstra implementation might overwrite the existing path count instead of accumulating additional paths. This implementation handles that correctly by checking new_dist == dist[neighbor] and adding the number of ways.

Another important case involves outdated heap entries. During Dijkstra's execution, a node may be pushed into the heap multiple times before its final shortest distance is determined. If we process outdated entries, we may perform unnecessary work or even corrupt path counts. The condition if current_dist > dist[node]: continue safely skips obsolete states.

Large edge weights are another common source of bugs. Since each edge weight may be as large as 10^9, total shortest distances can exceed normal 32 bit integer ranges when many edges are combined. The Go implementation uses int64 for distances to avoid overflow, while Python naturally supports arbitrarily large integers.

A final edge case involves graphs where the destination can be reached directly and indirectly with the same total cost. The algorithm correctly counts all such routes because every equally optimal relaxation contributes to the destination's ways count.