Advanced Graphs

Step 1 Understand it

Remember it by

Weighted edges? Dijkstra: always expand the cheapest known node next (a heap).

Watch it happen

The idea

When edges have different costs, BFS isn't enough. Dijkstra uses a min-heap to always settle the cheapest unsettled node. Related tools: Bellman-Ford when there's a limit on the number of edges (or negative weights), Prim's or Kruskal's for the cheapest way to connect everything (minimum spanning tree), and topological sort for ordering.

Picture it

flowchart LR
  S(("2: source")) -->|"1"| A(("1"))
  S -->|"1"| B(("3"))
  B -->|"1"| D(("4"))
  A -->|"3"| D

Analogy

Water spreading from a source through pipes of different lengths. It reaches near places first, and the first time it reaches a place is via the shortest route.

Where the analogy breaks

Water spreads everywhere at once; Dijkstra settles one node at a time. It also fails with negative edge costs, which water has no equivalent of.

Step 2 Recognise it

Words that signal it

• 'Minimum cost / time / delay' with weighted edges
• 'Within k stops' → Bellman-Ford (k + 1 rounds)
• 'Connect all points with minimum total cost' → minimum spanning tree
• 'Order of letters / tasks from rules' → topological sort
• 'Minimise the maximum along a path' (Swim in Rising Water) → Dijkstra on the max

Don't confuse it with

• Graphs (BFS): All edges cost the same → plain BFS. Different costs → Dijkstra.
• Dynamic Programming: Bellman-Ford is DP over the number of edges used — reach for it when the number of steps is limited.

Gut check

Shortest path, but the edges have different weights? → Dijkstra with a heap.

How to recognise it in an interview

The problem talks about 'Prerequisites', 'Cheapest network', 'Connecting all points', or gives an edges array WITH a third weight value.

Step 3 The template

The general shape. Adapt it to each problem rather than learning one solution per problem.

import heapq

def dijkstra(adj, source):
    # adj[u] = list of (v, cost)
    dist = {}
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if u in dist:
            continue                   # already settled with a cheaper cost
        dist[u] = d
        for v, cost in adj[u]:
            if v not in dist:
                heapq.heappush(heap, (d + cost, v))
    return dist

class Solution {
    // Union-Find (Disjoint Set) Template
    int[] parent;
    public int find(int i) {
        // Find root and compress path
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]); 
    }
    public boolean union(int i, int j) {
        int rootI = find(i), rootJ = find(j);
        if (rootI == rootJ) return false; // Already connected! (CYCLE FOUND)
        parent[rootI] = rootJ; // Connect them
        return true;
    }
}

Common mistakes

• Not skipping a node popped a second time (a stale, more expensive entry).
• Updating prices in place during a Bellman-Ford round, which lets one round use more than one extra edge — copy the array first.
• Using Dijkstra with a 'k stops' limit: the cheapest path may use too many stops.
• Confusing Dijkstra's algorithm (Weighted Shortest Path) with standard BFS (Unweighted Shortest Path).
• Forgetting to initialize the Parent array to parent[i] = i in a Union-Find object.

Step 4 Watch it run

Two problems, traced step by step exactly as the code runs.

import heapq
from collections import defaultdict

def network_delay_time(times, n, k):
    adj = defaultdict(list)
    for u, v, w in times:
        adj[u].append((v, w))
    dist, heap = {}, [(0, k)]
    while heap:
        d, u = heapq.heappop(heap)
        if u in dist:
            continue
        dist[u] = d
        for v, w in adj[u]:
            if v not in dist:
                heapq.heappush(heap, (d + w, v))
    return max(dist.values()) if len(dist) == n else -1

def find_cheapest_price(n, flights, src, dst, k):
    prices = [float('inf')] * n
    prices[src] = 0
    for _ in range(k + 1):                 # k stops = k + 1 flights
        tmp = prices[:]                    # copy: one more flight per round
        for u, v, w in flights:
            if prices[u] + w < tmp[v]:
                tmp[v] = prices[u] + w
        prices = tmp
    return prices[dst] if prices[dst] != float('inf') else -1

Step 5 Practise

Read each question and say the pattern and the trick out loud before you open the answer. Then solve it on LeetCode. Tick a problem once you've solved it on your own: it comes back for review tomorrow, then after 3, 7, 14 and 30 days, then every month, on the DSA page.

Medium

1. Mark "Network Delay Time" as solved Network Delay Time Medium

   A signal starts at node k; how long until every node receives it, with weighted travel times?

   Show answer

   Technique: Dijkstra

   The clue: Shortest times with weighted edges, from one source.

   The trick: Dijkstra from k; the answer is the largest shortest time (−1 if some node is never reached).

2. Mark "Min Cost to Connect All Points" as solved Min Cost to Connect All Points Medium

   Connect all points with the smallest total Manhattan distance.

   Show answer

   Technique: Minimum spanning tree (Prim's)

   The clue: 'Connect everything with minimum total cost'.

   The trick: Prim's: grow a tree from one point, always adding the cheapest edge to a new point (min-heap).

3. Mark "Cheapest Flights Within K Stops" as solved Cheapest Flights Within K Stops Medium

   Find the cheapest price from src to dst using at most k stops.

   Show answer

   Technique: Bellman-Ford with k + 1 rounds

   The clue: Cheapest path with a limit on the number of edges.

   The trick: Run k + 1 rounds of edge relaxation, copying the prices each round so each round adds only one flight.

Hard

1. Mark "Reconstruct Itinerary" as solved Reconstruct Itinerary Hard

   Use every ticket exactly once to build the itinerary from JFK, choosing the alphabetically smallest when there's a choice.

   Show answer

   Technique: Hierholzer's algorithm (Eulerian path)

   The clue: 'Use every edge exactly once'.

   The trick: Sort destinations; DFS taking the smallest ticket each time; add an airport to the route when it has no tickets left, then reverse.

2. Mark "Swim In Rising Water" as solved Swim In Rising Water Hard

   Water rises by 1 each second; find the earliest time you can swim from the top-left to the bottom-right.

   Show answer

   Technique: Dijkstra on the maximum along the path

   The clue: Minimise the highest cell you must pass through.

   The trick: Dijkstra where a path's cost is the largest height on it; pop cells in order of that cost.

3. Mark "Alien Dictionary" as solved Alien Dictionary Hard

   Given words sorted in an unknown alphabet, work out the letter order.

   Show answer

   Technique: Build a graph + topological sort

   The clue: An order between letters from comparisons = dependencies.

   The trick: Compare neighbouring words at their first different letter to get an edge; topologically sort; watch for 'abc' before 'ab' (invalid).

What to say in the interview

'Because the edges have weights (or strict prerequisites), standard BFS is insufficient. I'll need to use Dijkstra's Algorithm (or Union-Find) to solve this optimally.'

Follow-up prep

Can Dijkstra's handle negative weights? (No, you'd need Bellman-Ford).