Number of Ways to Arrive at Destination - Video Solutions

Problem Overview: Given n intersections and bidirectional roads with travel times, compute how many distinct ways you can reach node n-1 from node 0 using the minimum total time. The graph can contain multiple routes, but only paths with the shortest distance count. The result must be returned modulo 1e9 + 7.

Approach 1: Dijkstra's Algorithm with Path Counting (Time: O(E log V), Space: O(V + E))

This approach combines classic shortest path computation with dynamic counting of paths. Use an adjacency list and a min-heap priority queue to run Dijkstra from node 0. Maintain two arrays: dist[i] for the shortest distance to node i, and ways[i] for the number of shortest paths reaching that node. When relaxing an edge, update normally if a strictly shorter distance is found and copy the path count from the parent. If another path reaches the same node with the exact same shortest distance, add the parent’s path count instead of replacing it. This effectively layers a dynamic programming idea on top of Dijkstra. The priority queue ensures nodes are processed in increasing distance order, which guarantees correctness for weighted graphs with non‑negative edges.

Approach 2: Bellman-Ford Adaptation (Time: O(V * E), Space: O(V))

Another way to compute shortest paths is the Bellman-Ford relaxation process. Iterate over all edges up to V-1 times, updating distances similarly to standard Bellman-Ford. Alongside the distance array, track a ways[] array storing the number of shortest routes to each node. When a relaxation produces a smaller distance, copy the path count from the source node; when it produces the same distance, add the counts. This approach works even if the algorithm repeatedly revisits nodes because the relaxations converge toward the minimum distance. The drawback is performance: iterating over every edge for each pass makes it significantly slower than heap-based methods for dense graphs.

Recommended for interviews: The expected solution uses Dijkstra with path counting. Interviewers want to see that you recognize the problem as a weighted graph shortest-path problem and augment the algorithm to track the number of optimal routes. Starting from brute reasoning about shortest paths is fine, but implementing the heap-based solution demonstrates strong algorithmic intuition and efficient handling of weighted graphs.