How to Solve: Find the Shortest Path (Dijkstra’s Algorithm) – Complete Guide for FAANG Interviews

How to Solve: Find the Shortest Path (Dijkstra’s Algorithm) – Complete Guide for FAANG Interviews

? Introduction

"Dijkstra’s algorithm isn’t just a graph problem—it’s a signal to interviewers that you can optimize real-world systems. Master it, and you’ll solve 1 in 4 graph problems in FAANG interviews while proving you understand trade-offs between time, space, and edge cases."

? WHAT YOU NEED TO KNOW FIRST

Before diving into Dijkstra’s, ensure you understand: 1. Priority Queues (Min-Heaps) – How to extract the smallest element in O(log n) time. 2. Graph Representations – Adjacency lists vs. adjacency matrices (and when to use each). 3. Breadth-First Search (BFS) – The intuition behind exploring nodes level by level.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK (Mental Checklist)

Run this exact sequence for every Dijkstra’s problem:

1. Clarify the Graph Type
2. Directed or undirected?
3. Non-negative weights? (Dijkstra’s fails with negative weights—use Bellman-Ford instead.)

4. Sparse or dense? (Adjacency list for sparse, matrix for dense.)

5. Initialize Data Structures

6. dist array: Set all distances to ∞ except the start node (dist[start] = 0).
7. Priority queue: Push (0, start) (distance, node).

8. (Optional) visited set if the graph has cycles (rarely needed for Dijkstra’s).

9. Process Nodes in Priority Order

10. While the queue isn’t empty:

    • Pop the node with the smallest distance (current_dist, current_node).
    • If current_dist > dist[current_node], skip (lazy deletion).
    • For each neighbor:
    • Calculate new_dist = current_dist + edge_weight.
    • If new_dist < dist[neighbor], update dist[neighbor] and push (new_dist, neighbor) to the queue.

11. Terminate Early (If Applicable)

12. If the target node is popped from the queue, return dist[target] immediately.

13. Handle Edge Cases

14. Start node = target node? (Return 0.)
15. Disconnected graph? (Return -1 or ∞ for unreachable nodes.)

16. Multiple edges between nodes? (Keep the smallest weight.)

17. Return the Result

18. If the target is reachable, return dist[target].
19. If not, return -1 or ∞ (clarify with the interviewer).

? WORKED EXAMPLES

Example 1 – Basic: Shortest Path in a Weighted Graph

Problem: Given a graph with non-negative weights, find the shortest path from node 0 to node 3.

Graph:

0 --4--> 1
|        |
1        2
|        |
2 --3--> 3

Adjacency list:

graph = {

    0: [(1, 4), (2, 1)],

    1: [(3, 2)],

    2: [(1, 2), (3, 3)],

    3: []
}

Solution (Python):

import heapq

def dijkstra(graph, start, target):

    dist = {node: float('inf') for node in graph}

    dist[start] = 0

    pq = [(0, start)]


    while pq:

        current_dist, current_node = heapq.heappop(pq)

        if current_node == target:

            return current_dist

        if current_dist > dist[current_node]:

            continue  # Lazy deletion

        for neighbor, weight in graph[current_node]:

            new_dist = current_dist + weight

            if new_dist < dist[neighbor]:

                dist[neighbor] = new_dist

                heapq.heappush(pq, (new_dist, neighbor))

    return -1  # Target not reachable

print(dijkstra(graph, 0, 3))  # Output: 4 (0 → 2 → 1 → 3)

Time Complexity: O((V + E) log V) (each edge processed once, heap operations take O(log V)). Space Complexity: O(V) (for dist and the heap).

Why This Works: - The priority queue ensures we always expand the closest node first. - Lazy deletion avoids reprocessing outdated entries. - The dist array guarantees we only update paths when we find a shorter one.

Example 2 – Medium: Shortest Path with Multiple Targets

Problem: Find the shortest path from node 0 to all other nodes in the graph.

Graph:

0 --1--> 1 --2--> 2
 \       /
  4     1

   \   /

     3

Adjacency list:

graph = {

    0: [(1, 1), (3, 4)],

    1: [(2, 2), (3, 1)],

    2: [],

    3: []
}

Solution (Python):

import heapq

def dijkstra_all_nodes(graph, start):

    dist = {node: float('inf') for node in graph}

    dist[start] = 0

    pq = [(0, start)]


    while pq:

        current_dist, current_node = heapq.heappop(pq)

        if current_dist > dist[current_node]:

            continue

        for neighbor, weight in graph[current_node]:

            new_dist = current_dist + weight

            if new_dist < dist[neighbor]:

                dist[neighbor] = new_dist

                heapq.heappush(pq, (new_dist, neighbor))

    return dist

print(dijkstra_all_nodes(graph, 0))  # Output: {0: 0, 1: 1, 2: 3, 3: 2}

Time Complexity: O((V + E) log V) (same as before). Space Complexity: O(V).

Why This Works: - The algorithm naturally computes shortest paths to all nodes. - The dist array is returned directly, giving distances to every node.

Example 3 – Hard/Follow-up: Shortest Path with Constraints (e.g., "Cheapest Flights Within K Stops")

Problem: Given n cities (nodes) and flights (edges), find the cheapest price from src to dst with at most k stops.

Graph:

0 --100--> 1 --100--> 2
 \         /
  500     100

   \     /

     3

Adjacency list:

flights = [[0,1,100],[1,2,100],[0,3,500],[3,1,100]]
n = 4
src = 0
dst = 2
k = 1

Solution (Python):

import heapq

def findCheapestPrice(n, flights, src, dst, k):

    graph = {i: [] for i in range(n)}

    for u, v, w in flights:

        graph[u].append((v, w))


    # Priority queue: (current_cost, current_node, stops_used)

    pq = [(0, src, 0)]

    # Track the minimum cost to reach each node with <= k stops

    min_cost = {node: float('inf') for node in range(n)}

    min_cost[src] = 0


    while pq:

        cost, node, stops = heapq.heappop(pq)

        if node == dst:

            return cost

        if stops > k:

            continue

        for neighbor, weight in graph[node]:

            new_cost = cost + weight

            if new_cost < min_cost[neighbor]:

                min_cost[neighbor] = new_cost

                heapq.heappush(pq, (new_cost, neighbor, stops + 1))

    return -1

print(findCheapestPrice(n, flights, src, dst, k))  # Output: 200 (0 → 1 → 2)

Time Complexity: O((V + E) log V) (same as Dijkstra’s, but with an extra constraint). Space Complexity: O(V).

Why This Works: - The priority queue now tracks (cost, node, stops), ensuring we respect the k stops limit. - We skip paths that exceed k stops, even if they’re cheaper (constraint handling).

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. Dijkstra’s is your go-to for shortest paths in graphs with non-negative weights. Here’s the playbook:

1. Clarify the graph: Directed? Undirected? Non-negative weights? Sparse or dense?
2. Initialize: dist array with ∞, set dist[start] = 0, and push (0, start) into a min-heap.
3. Process nodes: Pop the closest node, skip if outdated, and relax all its neighbors.
4. Terminate early if you reach the target, or return the full dist array if needed.
5. Edge cases: Start = target? Disconnected graph? Multiple edges? Handle them explicitly.

Remember: The priority queue is your best friend. Lazy deletion keeps you efficient. And if weights can be negative, pivot to Bellman-Ford. Now go crush that interview!

? Final Notes

• Practice Problems:
• LeetCode 743. Network Delay Time (Basic)
• LeetCode 1514. Path with Maximum Probability (Medium)
• LeetCode 787. Cheapest Flights Within K Stops (Hard)
• Whiteboard Tip: Draw the graph first, then walk through the algorithm step-by-step.
• Time Management: If stuck, fall back to BFS (for unweighted graphs) or Bellman-Ford (for negative weights).

You’ve got this! ?