1976. Number of Ways to Arrive at Destination

How to solve Number of Ways to Arrive at Destination (LeetCode 1976): the approach in brief

The problem

You are in a city that consists of n intersections numbered from 0 to n - 1 with bi-directional roads between some intersections. The inputs are generated such that you can reach any intersection from any other intersection and that there is at most one road between any two intersections.

Pattern

Number of Ways to Arrive at Destination is a Graph Traversal Patterns (DFS & BFS) problem, in the Shortest Path (Dijkstra's Algorithm) subpattern. The pattern covers DFS/BFS traversal, topological sort, shortest paths, Union-Find, and MST

Master Dijkstra's algorithm for finding shortest paths in weighted graphs with non-negative edges.

Approach outline

1. First use any shortest path algorithm to get edges where dist[u] + weight = dist[v], here dist[x] is the shortest distance between node 0 and x
2. Using those edges only the graph turns into a dag now we just need to know the number of ways to get from node 0 to node n - 1 on a dag using dp

Complexity

The reference solution runs in O((|E| + |V|) * log|V|) time and O(|E| + |V|) space.