Limited Time Offer:Up to 25% off Hello Interview Premium

⌘K

Tutor

Get Premium

Graphs

Overview

Pre-Requisite: Depth-First Search, Breadth-First Search

Finding the shortest path between nodes is one of the most fundamental graph problems. But here's the thing, there's no single "shortest path algorithm." The right choice depends entirely on your graph's properties.

This page gives you a mental framework for picking the right algorithm.

The Core Question

Before writing any code, ask yourself:

What do I know about the edge weights?

This single question determines which algorithm fits. Here's the decision tree:

Graph Type	Algorithm	Time Complexity
Unweighted (all edges = 1)	BFS	O(V + E)
Non-negative weights	Dijkstra	O((V + E) log V)
Negative weights allowed	Bellman-Ford	O(V · E)
All pairs, small graph	Floyd-Warshall	O(V³)

Let's break down each one.

1. BFS: When All Edges Are Equal

If every edge has the same cost (or weight = 1), BFS is your shortest path algorithm.

Why it works: BFS explores nodes level by level. The first time you reach a node, you've found the shortest path to it. No other path can be shorter because all edges cost the same.

Walkthrough

Watch BFS find shortest paths from node 0. Notice how distances increase level by level — all nodes at distance 1 are found before any node at distance 2.

Visualization


def bfs_shortest_path(graph, start):
    distances = {start: 0}
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        
        for neighbor in graph[node]:
            if neighbor not in distances:
                distances[neighbor] = distances[node] + 1
                queue.append(neighbor)
    
    return distances

BFS shortest path

0 / 12

BFS shortest path from node 0

Complexity

Time: O(V + E) — Each node and edge visited once

Space: O(V) — Queue and distances map

When to Use BFS

Grid navigation (moving up/down/left/right)
Unweighted graph traversal
Finding minimum number of steps/moves

Problems That Use BFS for Shortest Path

Minimum Knight Moves — Classic grid BFS
Rotting Oranges — Multi-source BFS
01-Matrix — Distance from each cell to nearest 0

If a problem asks for "minimum moves" or "shortest path" in a grid or unweighted graph, try BFS first. It's simpler and often sufficient.

2. Dijkstra's Algorithm: The Workhorse

Dijkstra's is the most important shortest path algorithm for interviews. It handles graphs where edges have different positive weights.

The idea: Always expand the cheapest unexplored node. Use a min-heap (priority queue) to efficiently find it.

Walkthrough

Watch Dijkstra greedily expand from the node with the smallest distance. The heap always gives us the cheapest unexplored node.

Visualization


def dijkstra(graph, start):
    distances = {start: 0}
    heap = [(0, start)]
    
    while heap:
        dist, node = heapq.heappop(heap)
        
        if dist > distances.get(node, float('inf')):
            continue
        
        for neighbor, weight in graph[node]:
            new_dist = dist + weight
            if new_dist < distances.get(neighbor, float('inf')):
                distances[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))
    
    return distances

Dijkstra's algorithm

0 / 25

Dijkstra's algorithm from node 0

Why It Works

Dijkstra is greedy — it always processes the node with the smallest known distance. Because all edge weights are non-negative, once we've processed a node, we've found its shortest path. No later discovery can improve it.

Dijkstra fails with negative edge weights. If an edge can reduce the total cost, the greedy assumption breaks down.

Complexity

Time: O((V + E) log V) with a binary heap

Each node is added to the heap at most once: O(V log V)
Each edge might trigger a heap update: O(E log V)

Space: O(V) for the distances map and heap

When to Use Dijkstra

Weighted graphs with non-negative edges
Finding shortest path from one source to all nodes
Problems involving "minimum cost" or "minimum time"

Classic Dijkstra Problems

Network Delay Time — How long until all nodes receive a signal?
Path With Minimum Effort — Minimize the maximum height difference along the path
Cheapest Flights Within K Stops — Shortest path with a constraint (uses modified state)

3. Bellman-Ford: When Negative Weights Exist

Bellman-Ford handles graphs with negative edge weights and can detect negative cycles.

The idea: Relax all edges V-1 times. Each iteration guarantees we've found shortest paths of increasing length.

Walkthrough

Watch Bellman-Ford relax edges iteratively. Notice the negative edge from 1→2 (weight -3) — Dijkstra would fail here, but Bellman-Ford handles it correctly.

Visualization


def bellman_ford(edges, n, start):
    distances = [float('inf')] * n
    distances[start] = 0
    
    for _ in range(n - 1):
        for u, v, weight in edges:
            if distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight
    
    # Check for negative cycles
    for u, v, weight in edges:
        if distances[u] + weight < distances[v]:
            return None  # Negative cycle
    
    return distances

Bellman-Ford algorithm

0 / 16

Bellman-Ford with a negative edge

Why V-1 Iterations?

A shortest path can have at most V-1 edges (visiting all V nodes without cycles). Each iteration finds paths that are one edge longer. After V-1 iterations, we've considered all possible shortest paths.

Complexity

Time: O(V · E) — Much slower than Dijkstra for large graphs

Space: O(V) for the distances array

When to Use Bellman-Ford

Graph has negative edge weights
Need to detect negative cycles
Problems involving arbitrage or exchange rates

In interviews, Bellman-Ford is more commonly discussed than implemented. Know why Dijkstra fails with negative weights and how Bellman-Ford fixes it.

4. Floyd-Warshall: All Pairs Shortest Path

What if you need the shortest path between every pair of nodes? Running Dijkstra V times works, but Floyd-Warshall is more elegant for dense graphs or small V.

The idea: Dynamic programming. For each node k, check if using k as an intermediate node improves the path from i to j.

Walkthrough

Watch Floyd-Warshall build the all-pairs distance matrix. For each intermediate node k (highlighted), we check if going through k gives a shorter path from i to j.

Visualization


def floyd_warshall(graph, n):
    dist = [[float('inf')] * n for _ in range(n)]
    
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in graph:
        dist[u][v] = w
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

Floyd-Warshall algorithm

0 / 90

Floyd-Warshall building distance matrix

The Key Insight

After considering node k as an intermediate, dist[i][j] holds the shortest path from i to j using only nodes 0 through k as intermediates. By the end, we've considered all possible intermediate nodes.

Complexity

Time: O(V³) — Three nested loops over all vertices

Space: O(V²) — The distance matrix

When to Use Floyd-Warshall

Need distances between all pairs
Small number of nodes (V ≤ 400 or so)
Dense graphs where E ≈ V²

Classic Floyd-Warshall Problem

Find the City With the Smallest Number of Neighbors at a Threshold Distance — Count reachable cities for each starting city

Quick Reference

Here's your cheat sheet for interviews:

Algorithm Selection

Situation	Use This
All edges weight 1	BFS
Different positive weights	Dijkstra
Negative weights possible	Bellman-Ford
Need all pairs	Floyd-Warshall
Weights are 0 or 1 only	0-1 BFS (optimization)

Complexity Comparison

Algorithm	Time	Space
BFS	O(V + E)	O(V)
Dijkstra	O((V + E) log V)	O(V)
Bellman-Ford	O(V · E)	O(V)
Floyd-Warshall	O(V³)	O(V²)

Common Interview Patterns

Pattern 1: Modified State

Sometimes the shortest path depends on more than just the current node. For example:

"Cheapest flights with at most K stops" — State is (node, stops_remaining)
"Shortest path with keys and doors" — State is (node, keys_collected)

The algorithm stays the same, but your "node" becomes a tuple of (position, extra_state).

Pattern 2: Multi-Source BFS

When finding shortest distances from multiple starting points simultaneously:

Add all sources to the queue initially
BFS will naturally find the closest source for each node

Examples: Rotting Oranges, 01-Matrix

Pattern 3: Reverse Thinking

Sometimes it's easier to think backwards:

Instead of "shortest path from A to B", think "shortest path from B to A"
Instead of "can I reach the target?", think "which nodes can reach the target?"

Key Takeaways

BFS handles unweighted graphs — It's simpler than you think. Many "shortest path" problems are just BFS.
Dijkstra is your default for weighted graphs — Learn it cold. It appears in ~70% of weighted shortest path interview problems.
Know when algorithms fail — Dijkstra fails with negative weights. BFS fails with varying weights. Understanding why is more valuable than memorizing implementations.
State modification is common — Real interview problems often add constraints that require tracking extra state beyond just the current node.

Purchase Premium to Access

This article is only available to Premium users.

Purchase Premium

Graphs

Overview

The Core Question

1. BFS: When All Edges Are Equal

Walkthrough

Complexity

When to Use BFS

Problems That Use BFS for Shortest Path

2. Dijkstra's Algorithm: The Workhorse

Walkthrough

Why It Works

Complexity

When to Use Dijkstra

Classic Dijkstra Problems

3. Bellman-Ford: When Negative Weights Exist

Walkthrough

Why V-1 Iterations?

Complexity

When to Use Bellman-Ford

4. Floyd-Warshall: All Pairs Shortest Path

Walkthrough

The Key Insight

Complexity

When to Use Floyd-Warshall

Classic Floyd-Warshall Problem

Quick Reference

Algorithm Selection

Complexity Comparison

Common Interview Patterns

Pattern 1: Modified State

Pattern 2: Multi-Source BFS

Pattern 3: Reverse Thinking

Key Takeaways

Purchase Premium to Access

This article is only available to Premium users.

The best mocks on the market.

Questions

Learn

Links

Legal

Contact