Number of Ways to Arrive at Destination

Problem Overview

You are given an undirected weighted graph with V vertices and a list of edges. Each edge represents the time required to travel between two nodes.

The goal is:

• Find the shortest time to travel from node 0 to node V - 1

• Return the number of different ways to reach the destination using that shortest time

Core Concept

This problem is an extension of the classic Dijkstra’s Algorithm.

Normally, Dijkstra helps us find:

• Shortest distance from source to all nodes

But here, we also need:

• Number of ways to reach each node with that shortest distance

Key Idea

We maintain two arrays:

1. dist[]

   • Stores the shortest distance to each node

2. ways[]

   • Stores the number of shortest ways to reach each node

Algorithm Strategy

Step 1: Build Graph

• Use an adjacency list to store neighbors and weights

Step 2: Initialize

• dist[0] = 0 → starting point

• ways[0] = 1 → only one way to start

• All other distances = ∞

Step 3: Apply Dijkstra (Min Heap)

• We use a PriorityQueue (Min Heap) to always process the node with the smallest distance

Step 4: Relaxation Logic (Important)

For every adjacent node:

Case 1: Shorter Path Found

if (newDist < dist[adjNode])

• Update shortest distance

• Copy number of ways

Why copy?

• Because this is a better path, so previous ways are irrelevant

Case 2: Another Shortest Path Found

else if (newDist == dist[adjNode])

• Add number of ways

Why add?

• Because we found another route with same shortest time

Visualization (Simple Example)

• 0 ----(5)----> 3

• \

• (2)

• \

• 1 ----(3)----> 3

Shortest time to reach node 3 = 5

Paths:

• 0 → 3

• 0 → 1 → 3

Total ways = 2

Complexity Analysis

Java Implementation

import java.util.*;

class Solution {

    public int countPaths(int V, int[][] edges) {

        final int MOD = 1_000_000_007;

        // Step 1: Build graph
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            graph.add(new ArrayList<>());
        }

        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            graph.get(u).add(new int[]{v, w});
            graph.get(v).add(new int[]{u, w});
        }

        // Step 2: Distance & ways
        long[] dist = new long[V];
        long[] ways = new long[V];
        Arrays.fill(dist, Long.MAX_VALUE);

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

        // Step 3: Min Heap
        PriorityQueue<long[]> pq = new PriorityQueue<>(
            (a, b) -> Long.compare(a[0], b[0])
        );

        pq.offer(new long[]{0, 0}); // {distance, node}

        while (!pq.isEmpty()) {

            long[] curr = pq.poll();
            long d = curr[0];
            int node = (int) curr[1];

            if (d > dist[node]) continue;

            for (int[] neighbor : graph.get(node)) {

                int adjNode = neighbor[0];
                int weight = neighbor[1];
                long newDist = d + weight;

                if (newDist < dist[adjNode]) {

                    dist[adjNode] = newDist;
                    ways[adjNode] = ways[node];

                    pq.offer(new long[]{newDist, adjNode});
                }
                else if (newDist == dist[adjNode]) {

                    ways[adjNode] = (ways[adjNode] + ways[node]) % MOD;
                }
            }
        }

        return (int)(ways[V - 1] % MOD);
    }
}

Summary

This problem extends Dijkstra’s Algorithm by not only computing the shortest distance but also tracking the number of shortest paths to each node. By maintaining both distance and ways arrays and carefully updating them during relaxation, we can efficiently determine how many minimum-time paths exist from the source to the destination with a time complexity of O(E log V).