DSA Graphs

Shortest Path Algorithms

The query hits at rush hour: minimize minutes, not hops. BFS gives fewest roads; Dijkstra needs non-negative travel times; a rebate edge needs Bellman-Ford. Name the before naming an algorithm.

“Shortest path” is a family. Fix source/target shape (, pair, multi-source, ), then do the : state, transition, cost, unreachable.

Decision journey

Query shape

Single source, pair, multi-source, or all pairs?

Unit, ≥0, negatives, or DAG?

Pick algorithm

BFS / Dijkstra / Bellman-Ford / Floyd / Johnson.

Stop rule

When is the target finalized, not merely discovered?

What actually happens

Naive idea: always BFS, or always Dijkstra. Breaks when weights are not 1, or when a negative edge invalidates the settled-set proof.

Better idea: write the contract first. Unweighted → BFS. Non-negative → Dijkstra. Negatives → Bellman-Ford (or DAG topo). Many pairs on dense graphs → Floyd-Warshall.

The improved design still fails when you stop Dijkstra on first push of the target, treat unreachable as 0, or model the wrong state space (forgetting a mode flag that edges depend on).

Invariant (chooser)

Only use an algorithm whose correctness assumptions match the graph. If the weight contract is violated, the “shortest” array is not a shortest-path certificate.

How to choose a shortest-path algorithm

1. Unit weights? BFS: O(V+E), and first discovery is optimal.

2. Non-negative? Dijkstra. Negatives and cycles possible? Bellman-Ford.

3. All pairs on small V? Floyd-Warshall O(V³). Sparse mixed signs: consider Johnson.

Quantitative check

V=500 all-pairs: Floyd ≈ 1.25×10⁸ ops. Same V sparse E=2000 with non-negative weights: 500 Dijkstra runs ≈ 500·(V+E)log V ≈ a few×10⁷ heap ops: often better.

Start with the contract

“Shortest path” is a family of problems. Before naming an algorithm, state what is being minimized, which sources and targets matter, and what the graph guarantees.

Single source

One source to every vertex. BFS, Dijkstra, DAG relaxation, and Bellman–Ford naturally compute this shape.

Single pair

One source and one target. Stop BFS on discovery; stop Dijkstra only when the target is popped with its current distance.

Multi-source

Seed every source with distance zero. The result is distance to the nearest source: no synthetic super-source is required in code.

All pairs

For many source queries, consider Floyd–Warshall in O(V³), repeated Dijkstra, or Johnson’s algorithm for sparse graphs.

Modeling comes first: a vertex represents state, an edge represents one legal transition, and its weight is the incremental cost. Confirm whether edges are directed, whether duplicate edges exist, and what “unreachable” must return.

Algorithm chooser

Select a weight contract to see the fastest standard algorithm whose correctness proof the contract permits.

Shortest-path decision laboratory

Change the graph contract. The best algorithm follows from structure and weight constraints, not from memorizing a favorite template.

Costs vary, but every edge weight is at least zero.

Choose

Dijkstra + min-heap

O((V + E) log V)

Correctness permission

Once the minimum tentative distance is popped, non-negative edges cannot create a cheaper later route.

Why not the tempting alternative?

Plain BFS optimizes edge count, not weight; Bellman–Ford gives up the useful greedy ordering.

Interview signal

Road distance, latency, effort, or any weighted cost with an explicit non-negative guarantee.

🎮 Interactive Demo (Dijkstra)

Watch how Dijkstra's algorithm explores the graph, always picking the "cheapest" known path to extend.

Start:

Ready to find shortest path!

A∞

B∞

C∞

D∞

E∞

Priority Queue

Queue is empty

Sorted by distance (Min-Heap)

⚔️ Algorithm Showdown

Algorithm	Graph Type	Weights	Time Complexity
BFS	Unweighted	N/A (All 1)	O(V + E)
0–1 BFS	Weighted + deque	Only 0 or 1	O(V + E)
DAG relaxation	Directed acyclic	Any finite weight	O(V + E)
Dijkstra	Weighted	Non-negative	O((V+E) log V)
Bellman-Ford	Weighted	Can be Negative	O(V × E)

Relaxation, paths, and heuristics

Shortest-path algorithms are variations on relaxation: if dist[u] + w(u,v) < dist[v], improve dist[v]. Dijkstra's greedy order works because non-negative weights prevent future shortcuts from invalidating settled vertices; Bellman–Ford relaxes enough rounds to propagate negative edges without that guarantee.

Store a parent pointer whenever dist[v] improves to reconstruct the path. For single-pair queries on large road graphs, bidirectional Dijkstra or A* (priority = dist + heuristic to goal) cuts explored vertices dramatically when a good heuristic exists.

Relaxation is the shared primitive

Edge u → v with weight w

if dist[u] ≠ ∞ and dist[u] + w < dist[v]

dist[v] = dist[u] + w

parent[v] = u

The invariant behind `dist[]`

Witness: every finite dist[v] is the cost of an actual discovered source-to-v walk.
Upper bound: therefore dist[v] never claims a value below the true finite optimum.
Monotonic improvement: relaxation only decreases tentative values.
Schedule supplies finality: BFS layers, deque order, topological order, heap order, or V−1 passes determine when all necessary witnesses have propagated.

Never evaluate INF + weight. Infinity means “no path witness yet,” and arithmetic on a sentinel can overflow into a fake negative distance. Guard reachability before every relaxation and use long for accumulated costs in Java.

Worked relaxation trace

For edges S→A (7), S→B (2), B→A (1), and A→T (3), each successful relaxation replaces both a distance and its path witness.

Processed evidence	dist[A]	dist[B]	dist[T]	Parent change
Initialize S	∞	∞	∞	none
S→A, S→B	7	2	∞	A←S, B←S
B→A improves 7 to 3	3	2	∞	A←B
A→T	3	2	6	T←A

Walking parents backward gives T←A←B←S; reverse it to return S→B→A→T. If the target remains at infinity, return an empty/absent result, not a one-vertex “path.”

💡 Pro Tip: Choosing the Right Tool

Always start by checking your edge weights! If they are all equal (unweighted), BFS is the fastest (O(V+E)). If they are non-negative, Dijkstra is the standard choice. Only use Bellman-Ford if you suspect negative weights or need to detect negative cycles, as it's significantly slower.

💻 Implementation: BFS (Unweighted Shortest Path)

For unweighted graphs, BFS is the optimal shortest path algorithm. It explores layer by layer, guaranteeing the first time we reach a node, it's via the shortest path.

Python

python

from collections import deque

def bfs_shortest_path(graph, start, end):
    """
    Find shortest path in unweighted graph using BFS
    
    Args:
        graph: Adjacency list {node: [neighbors]}
        start: Start node
        end: Target node
    
    Returns:
        List of nodes in path, or None if no path
    """
    queue = deque([(start, [start])])
    visited = set([start])
    
    while queue:
        current, path = queue.popleft()
        
        if current == end:
            return path
        
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
                
    return None

# Example Usage
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

path = bfs_shortest_path(graph, 'A', 'F')
print(f"Shortest Path: {path}")
# Output: Shortest Path: ['A', 'C', 'F']

Java

java

import java.util.*;

public class BFSShortestPath {
    public static List<String> bfsShortestPath(Map<String, List<String>> graph, String start, String end) {
        Queue<List<String>> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        
        List<String> initialPath = new ArrayList<>();
        initialPath.add(start);
        queue.add(initialPath);
        visited.add(start);
        
        while (!queue.isEmpty()) {
            List<String> path = queue.poll();
            String current = path.get(path.size() - 1);
            
            if (current.equals(end)) {
                return path;
            }
            
            if (graph.containsKey(current)) {
                for (String neighbor : graph.get(current)) {
                    if (!visited.contains(neighbor)) {
                        visited.add(neighbor);
                        List<String> newPath = new ArrayList<>(path);
                        newPath.add(neighbor);
                        queue.add(newPath);
                    }
                }
            }
        }
        
        return null;
    }

    public static void main(String[] args) {
        Map<String, List<String>> graph = new HashMap<>();
        graph.put("A", Arrays.asList("B", "C"));
        graph.put("B", Arrays.asList("A", "D", "E"));
        graph.put("C", Arrays.asList("A", "F"));
        graph.put("D", Arrays.asList("B"));
        graph.put("E", Arrays.asList("B", "F"));
        graph.put("F", Arrays.asList("C", "E"));

        List<String> path = bfsShortestPath(graph, "A", "F");
        System.out.println("Shortest Path: " + path);
        // Output: Shortest Path: [A, C, F]
    }
}

Memory-efficient BFS paths

Storing the full path in every queue entry (as in the demo snippet) is simple but uses O(V²) memory in the worst case. Production code keeps only (vertex, parent) or a separate parent[] map and rebuilds the path by walking backward from the goal.

Linear-time weighted special cases in Java

A heap is not the default for every weighted graph. Restricted weights or acyclic structure provide stronger ordering for free.

0–1 BFS · deque

java

import java.util.*;

final class ZeroOneBfs {
    static final long INF = Long.MAX_VALUE;

    static final class Edge {
        final int to, weight;
        Edge(int to, int weight) {
            if (weight != 0 && weight != 1) {
                throw new IllegalArgumentException("0-1 BFS needs weights 0 or 1");
            }
            this.to = to;
            this.weight = weight;
        }
    }

    static final class State {
        final int vertex;
        final long distance;
        State(int vertex, long distance) {
            this.vertex = vertex;
            this.distance = distance;
        }
    }

    static long[] shortestPaths(List<Edge>[] graph, int source) {
        long[] dist = new long[graph.length];
        Arrays.fill(dist, INF);
        dist[source] = 0L;

        Deque<State> deque = new ArrayDeque<>();
        deque.addFirst(new State(source, 0L));

        while (!deque.isEmpty()) {
            State state = deque.removeFirst();
            int u = state.vertex;
            if (state.distance != dist[u]) continue; // stale state

            for (Edge edge : graph[u]) {
                long candidate = dist[u] + edge.weight; // +0/+1 cannot overflow here
                if (candidate >= dist[edge.to]) continue;

                dist[edge.to] = candidate;
                State next = new State(edge.to, candidate);
                if (edge.weight == 0) deque.addFirst(next);
                else deque.addLast(next);
            }
        }
        return dist; // INF means unreachable
    }
}

DAG shortest path

java

import java.util.*;

final class DagShortestPath {
    static final long INF = Long.MAX_VALUE;

    static final class Edge {
        final int to;
        final long weight; // may be negative
        Edge(int to, long weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    // topologicalOrder must contain every vertex exactly once.
    static long[] shortestPaths(
            List<Edge>[] graph, int[] topologicalOrder, int source) {
        long[] dist = new long[graph.length];
        Arrays.fill(dist, INF);
        dist[source] = 0L;

        for (int u : topologicalOrder) {
            if (dist[u] == INF) continue; // never add to the sentinel

            for (Edge edge : graph[u]) {
                // Explicitly fail on impossible input magnitude; never wrap silently.
                long candidate = Math.addExact(dist[u], edge.weight);
                if (candidate < dist[edge.to]) {
                    dist[edge.to] = candidate;
                }
            }
        }
        return dist;
    }
}

Checklist before you lock the approach

Define state and edge direction. Say what a path cost means.
Ask for constraints. Weight domain, V/E scale, cycles, and sparse versus dense.
Choose the schedule. Queue, deque, topological order, heap, or repeated edge passes.
State the invariant. Explain why a popped/discovered value is final, or why more passes are needed.
Specify output semantics. Distance only or actual path; empty result for unreachable; special status for a relevant negative cycle.
Test adversarial cases. Duplicate edges, zero weights, disconnected vertices, source equals target, overflow, and negative cycles unreachable from the source.

Bug	Why it fails	Guardrail
BFS on weighted edges	Fewest edges need not be cheapest.	Inspect the weight domain first.
Marking too late	BFS can enqueue a vertex many times.	Mark on enqueue, not dequeue.
Stopping Dijkstra on push	A later route may lower the target.	Stop when its current entry is popped.
Returning fake paths	A default parent can fabricate connectivity.	Check finite reachability before rebuilding.

Short takeaway

Pick the shortest-path algorithm from the weight contract and query shape, not from habit. BFS for unit weights, Dijkstra for non-negative, Bellman-Ford when negatives matter, Floyd or Johnson for all pairs.

Exercises

A routing graph has mostly non-negative times plus one promotional “−5 minute” edge. Which algorithm is safe, and what extra outcome must you report if that edge sits on a negative cycle reachable from the depot?
You need distances from every city to every city on V=200, E=800, non-negative. Compare Floyd-Warshall with repeated Dijkstra.
Multi-source “distance to nearest warehouse.” How do you seed the algorithm without inventing a fake super-source vertex in code?

Primary sources

Cormen et al., CLRS: Single-source and all-pairs shortest paths chapters.
Dijkstra (1959); Bellman (1958); Floyd (1962) / Warshall (1962).
Johnson, D. B.: Efficient algorithms for shortest paths in sparse networks.

Shortest Path Algorithms

What actually happens

How to choose a shortest-path algorithm

Quantitative check

Start with the contract

Single source

Single pair

Multi-source

All pairs

Algorithm chooser

Shortest-path decision laboratory

Correctness permission

Why not the tempting alternative?

Interview signal

🎮 Interactive Demo (Dijkstra)

Priority Queue

⚔️ Algorithm Showdown

Relaxation, paths, and heuristics

Relaxation is the shared primitive

The invariant behind dist[]

Worked relaxation trace

💡 Pro Tip: Choosing the Right Tool

💻 Implementation: BFS (Unweighted Shortest Path)

Python

Java

Memory-efficient BFS paths

Linear-time weighted special cases in Java

0–1 BFS · deque

DAG shortest path

Checklist before you lock the approach

Short takeaway

Exercises

Primary sources

The invariant behind `dist[]`