Minimum Time to Reach Destination in Directed Graph - Solution & Explanation

Problem Overview: You are given a directed graph where each edge represents the time required to travel between two nodes. Starting from a source node, compute the minimum time required to reach a destination node. If multiple paths exist, you must choose the one with the smallest total travel time.

Approach 1: DFS with Path Exploration (Brute Force) (Time: O(V! ) worst case, Space: O(V))

The most direct idea is to explore every possible path from the source to the destination and track the total travel time for each path. Use a depth‑first search and maintain a running sum of edge weights while marking nodes as visited to avoid cycles. Whenever you reach the destination, update the minimum time found so far. This approach works for very small graphs but quickly becomes impractical because the number of possible paths grows exponentially. It mainly serves as a conceptual baseline before applying shortest path algorithms.

Approach 2: Dijkstra’s Algorithm with Min Heap (Optimal) (Time: O((V + E) log V), Space: O(V))

This problem is a classic single‑source shortest path scenario on a weighted directed graph. The optimal solution uses Dijkstra’s algorithm with a min heap (priority queue). First build an adjacency list representing outgoing edges for each node. Maintain a distance array where dist[i] stores the shortest known time to reach node i. Push the source node into a min heap with distance 0.

At each step, pop the node with the smallest current travel time. For each outgoing edge, compute the candidate time by adding the edge weight to the current distance. If this value is smaller than the stored distance, update it and push the neighbor into the heap. Because the heap always expands the node with the smallest known distance, the first time you finalize the destination node you have the optimal answer. This approach efficiently handles large graphs and sparse edge sets.

The algorithm relies heavily on data structures commonly used in graph problems, especially adjacency lists and priority queues. The heap operations ensure efficient selection of the next closest node, which is the key idea behind many shortest path algorithms. Implementations typically use a binary heap from the heap (priority queue) toolkit.

Recommended for interviews: Interviewers expect the Dijkstra approach. Mentioning the brute‑force DFS first shows you understand the search space and why naive exploration fails. Switching to Dijkstra demonstrates knowledge of weighted graph traversal and the ability to reduce exponential search into an efficient O((V + E) log V) solution.