1976. Number of Ways to Arrive at Destination

[mah-shamim]

Topics: Dynamic Programming, Graph, Topological Sort, Shortest Path

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.

You are given an integer n and a 2D integer array roads where roads[i] = [ui, vi, timei] means that there is a road between intersections ui and vi that takes timei minutes to travel. You want to know in how many ways you can travel from intersection 0 to intersection n - 1 in the shortest amount of time.

Return the number of ways you can arrive at your destination in the shortest amount of time. Since the answer may be large, return it modulo 109 + 7.

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
• Explanation: 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
• Explanation: 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.

Hint:

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

[mah-shamim]

We need to determine the number of ways to travel from intersection 0 to intersection n-1 in the shortest possible time using bidirectional roads. The solution involves using Dijkstra's algorithm to find the shortest paths and then dynamic programming (DP) to count the number of ways to reach the destination using those shortest paths.

Approach

1. Compute Shortest Paths: Use Dijkstra's algorithm to compute the shortest time from intersection 0 to all other intersections. This helps in identifying the shortest paths.
2. Construct DAG: Build a Directed Acyclic Graph (DAG) where edges represent the shortest paths. For each road, check if it contributes to the shortest path in either direction and add the corresponding directed edge to the DAG.
3. Topological Sort: Sort nodes based on their shortest distance from 0. This ensures that we process nodes in the order of increasing distance, which is a valid topological order for the DAG.
4. Count Paths Using DP: Use dynamic programming to count the number of ways to reach each node from the start node (0) by processing nodes in topological order.

Let's implement this solution in PHP: 1976. Number of Ways to Arrive at Destination

<?php
/**
 * @param Integer $n
 * @param Integer[][] $roads
 * @return Integer
 */
function countPaths($n, $roads) {
    if ($n == 1) return 1;
    $mod = 1000000007;

    // Build adjacency list for Dijkstra's algorithm
    $adj = array_fill(0, $n, array());
    foreach ($roads as $road) {
        $u = $road[0];
        $v = $road[1];
        $t = $road[2];
        $adj[$u][] = array($v, $t);
        $adj[$v][] = array($u, $t);
    }

    // Dijkstra's algorithm to find shortest distances from node 0
    $dist = array_fill(0, $n, PHP_INT_MAX);
    $dist[0] = 0;
    $pq = new SplPriorityQueue();
    $pq->setExtractFlags(SplPriorityQueue::EXTR_BOTH);
    $pq->insert(array(0, 0), -0);

    while (!$pq->isEmpty()) {
        $elem = $pq->extract();
        $currentDist = -$elem['priority'];
        $u = $elem['data'][1];

        if ($currentDist > $dist[$u]) continue;

        foreach ($adj[$u] as $edge) {
            $v = $edge[0];
            $t = $edge[1];
            $newDist = $currentDist + $t;
            if ($newDist < $dist[$v]) {
                $dist[$v] = $newDist;
                $pq->insert(array($newDist, $v), -$newDist);
            }
        }
    }

    // Build the DAG adjacency list
    $dagAdj = array_fill(0, $n, array());
    foreach ($roads as $road) {
        $u = $road[0];
        $v = $road[1];
        $t = $road[2];
        if ($dist[$u] + $t == $dist[$v]) {
            $dagAdj[$u][] = $v;
        }
        if ($dist[$v] + $t == $dist[$u]) {
            $dagAdj[$v][] = $u;
        }
    }

    // Sort nodes based on their distance from 0
    $nodes = range(0, $n-1);
    usort($nodes, function ($a, $b) use ($dist) {
        return $dist[$a] - $dist[$b];
    });

    // Dynamic programming to count paths
    $dp = array_fill(0, $n, 0);
    $dp[0] = 1;
    foreach ($nodes as $u) {
        foreach ($dagAdj[$u] as $v) {
            $dp[$v] = ($dp[$v] + $dp[$u]) % $mod;
        }
    }

    return $dp[$n-1] % $mod;
}

// Example Test Cases
$n1 = 7;
$roads1 = [[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]];
echo countPaths($n1, $roads1) . "\n"; // Output: 4

$n2 = 2;
$roads2 = [[1,0,10]];
echo countPaths($n2, $roads2) . "\n"; // Output: 1
?>

Explanation:

1. Dijkstra's Algorithm: This algorithm efficiently computes the shortest path from the start node (0) to all other nodes using a priority queue. The shortest paths are stored in the dist array.
2. Constructing DAG: For each road, we check if it can be part of a shortest path in either direction. This helps in building the adjacency list for the DAG.
3. Topological Sort: Nodes are sorted by their shortest distance from 0 to ensure we process each node after all nodes that can reach it via shorter paths.
4. Dynamic Programming: Using the topological order, we count the number of ways to reach each node by summing the ways from all its predecessors in the DAG. This ensures we only consider paths that contribute to the shortest time.

This approach efficiently combines graph traversal and dynamic programming to solve the problem within the constraints.

[kovatz]

Thanks for solving the problem of "Number of Ways to Arrive at Destination"

[mah-shamim]

Thanks