Graph algorithms: BFS, DFS and shortest paths

In short

Graph traversal is the systematic visiting of every reachable vertex of a graph: breadth-first search (BFS) explores level by level using a queue, depth-first search (DFS) goes as deep as possible using a stack or recursion. Shortest-path algorithms build on them - BFS for unweighted graphs, Dijkstra for non-negative weights, Bellman-Ford for negative weights, Floyd-Warshall for all pairs. Together they are the most heavily examined part of the Algorithms paper in GATE CSE and appear in almost every DSA interview round at Amazon, Microsoft, Google, Flipkart, Walmart, Swiggy, Zomato, Oracle, Samsung and the Indian service companies' advanced tests. In practice they drive Google Maps and MapmyIndia routing, Delhi Metro route planners, OSPF and RIP in networks, delivery-fleet routing, dependency resolution in build tools and recommendation graphs.

Explained

Terminology and representation

• A graph G = (V, E): V vertices, E edges. Directed (edges are ordered pairs, arrows) or undirected; weighted (each edge has cost w(u,v)) or unweighted. Let n = |V|, m = |E|.
• Degree of a vertex = number of incident edges; in a directed graph, in-degree and out-degree. Handshaking lemma: sum of degrees = 2m.
• Simple graph: no self-loops, no parallel edges. Maximum edges = n(n−1)/2 undirected, n(n−1) directed. Sparse means m = O(n); dense means m ≈ n².
• Path, simple path (no repeated vertex), cycle, walk. Connected (undirected): a path exists between every pair. Strongly connected (directed): a directed path both ways. A DAG is a directed acyclic graph. A tree is connected and acyclic with exactly n−1 edges.
• Adjacency matrix A[n][n]: A[i][j] = 1 or w(i,j). Space Θ(n²); edge lookup O(1); listing neighbours O(n). Best for dense graphs and Floyd-Warshall.
• Adjacency list: array of n lists holding neighbours. Space Θ(n + m); listing neighbours O(deg); edge lookup O(deg). Default choice for BFS, DFS and Dijkstra.
• Edge list (array of triples u, v, w) - the natural input form for Bellman-Ford.

Breadth-first search (BFS)

• Visits all vertices at distance 1 from the source, then all at distance 2, and so on - a level-order traversal using a FIFO queue.
• Steps: (1) mark the source visited, dist = 0, push it; (2) pop u; (3) for each unvisited neighbour v, mark visited, dist[v] = dist[u] + 1, parent[v] = u, push v; (4) repeat until the queue is empty.
• Mark on enqueue, not on dequeue - otherwise a vertex can enter the queue many times.
• Complexity: O(V + E) time with an adjacency list (each vertex enqueued once, each edge scanned once - twice in an undirected graph), O(V²) with a matrix. Space O(V) for the queue, visited and dist arrays; the worst-case queue size is the widest level.
• Correctness: dist[v] produced by BFS equals the least number of edges from s to v. Proof outline by induction on the level: when a vertex at true distance k is dequeued, all vertices at distance k−1 have already been processed, and the queue is always non-decreasing in dist with at most two distinct values.
• Uses: shortest path in an unweighted graph; connected components; bipartite test (2-colouring); shortest path in a grid or maze; multi-source BFS (push all sources with dist 0 - gives the nearest source for every cell); level/depth of nodes in a tree; finding the diameter of a tree by two BFS runs; web crawling; peer-to-peer broadcast.
• 0-1 BFS: when all weights are 0 or 1, use a deque - push-front for a 0-edge, push-back for a 1-edge - giving shortest paths in O(V + E) without a heap.
• Bidirectional BFS: run BFS from source and target together; cuts the explored frontier from b^d to about 2·b^d/2.

Depth-first search (DFS)

• Follows one branch to exhaustion, then backtracks. Implemented by recursion (the call stack) or an explicit stack. Time O(V + E), space O(V); recursion depth can reach V, so a deep chain can overflow the stack - prefer an iterative version for very large graphs.
• Timestamps: a global clock gives each vertex a discovery time d[v] and a finish time f[v], with d[v] < f[v]. Parenthesis theorem: the intervals [d[v], f[v]] are either disjoint or nested; v is a descendant of u exactly when [d[v], f[v]] ⊂ [d[u], f[u]].
• Edge classification in a directed graph (relative to the DFS forest):
  • Tree edge - leads to an undiscovered vertex.
  • Back edge - leads to an ancestor (grey vertex, discovered but not finished). A back edge exists iff the graph has a cycle.
  • Forward edge - leads to a descendant already finished (d[u] < d[v]).
  • Cross edge - all others (d[u] > d[v], v already finished, not a descendant).
• In an undirected graph only tree and back edges occur; forward and cross edges cannot appear.
• White-grey-black colouring: white = undiscovered, grey = on the recursion stack, black = finished. Cycle detection in a directed graph = finding an edge to a grey vertex. In an undirected graph, a visited neighbour that is not the parent indicates a cycle (watch out for parallel edges).
• Uses built on DFS: topological sort (reverse order of finish times of a DAG); strongly connected components - Kosaraju's two-pass method (DFS, reverse the graph, DFS in decreasing finish time) and Tarjan's one-pass low-link method, both O(V + E); articulation points and bridges (low-link values); path existence; flood fill; maze generation; backtracking search; detecting cycles in dependency graphs.
• Kahn's algorithm gives a topological order using BFS instead: repeatedly output a vertex of in-degree 0 and decrement its neighbours' in-degrees; if fewer than V vertices are output, a cycle exists.

Relaxation and the single-source shortest-path framework

• Keep an estimate d[v] (initially 0 for the source, ∞ elsewhere) and a predecessor π[v]. Relaxing edge (u, v): if d[u] + w(u,v) < d[v], set d[v] = d[u] + w(u,v) and π[v] = u. Every shortest-path algorithm here is a different order of relaxations.
• Properties used in proofs: triangle inequality δ(s,v) ≤ δ(s,u) + w(u,v); upper-bound property d[v] ≥ δ(s,v) always; path-relaxation property - relaxing the edges of a shortest path in order fixes it.
• Optimal substructure: any sub-path of a shortest path is itself a shortest path - this is why greedy and dynamic-programming formulations both work.
• A shortest path is undefined (−∞) if a negative-weight cycle is reachable from s; shortest *simple* path with negative cycles is NP-hard. With non-negative weights a shortest path is always simple, so it uses at most V−1 edges.

Dijkstra's algorithm (non-negative weights)

• Greedy: maintain a set S of finalised vertices. Repeatedly extract the unfinalised vertex u with the smallest d[u], finalise it, and relax all its outgoing edges.
• Invariant: when u is extracted, d[u] = δ(s,u). Proof sketch - if not, the true shortest path to u leaves S at some vertex y with d[y] = δ(s,y) ≤ δ(s,u) < d[u], contradicting the choice of u as minimum. This argument needs non-negative weights; a single negative edge breaks it, because a later-discovered vertex could cheapen an already finalised one.
• Complexity by priority-queue choice:
  • simple array / linear scan: O(V²) - best for dense graphs (m ≈ n²);
  • binary heap (lazy deletion, the usual competitive-programming form): O((V + E) log V) ≈ O(E log V);
  • Fibonacci heap: O(E + V log V) - theoretically best, rarely implemented.
• Practical points: with a lazy heap, pop and skip stale entries (if dist_popped > d[u]: continue); stop early when the target is popped; store paths by following π backwards.
• Dial's algorithm / bucket queue: O(E + V·C) when weights are small integers bounded by C.
• A\* search adds a heuristic h(v): pop by d[v] + h(v). If h is admissible (never overestimates) the answer is optimal; if also consistent it never re-expands a node. With h ≡ 0, A* degenerates to Dijkstra. Used in map routing with straight-line distance as h.

Bellman-Ford, DAG relaxation and all-pairs methods

• Bellman-Ford: repeat V−1 times - relax every edge once. After pass i, all shortest paths using at most i edges are correct; since a shortest path has ≤ V−1 edges, V−1 passes suffice. Time O(V·E), space O(V).
  • Run one extra pass: if any edge still relaxes, a negative-weight cycle is reachable; the affected vertices can be marked −∞ by a further BFS/DFS from them.
  • Early exit when a pass makes no change. SPFA (queue-based Bellman-Ford) is much faster in practice but still O(V·E) in the worst case.
  • Handles negative edges - essential in currency arbitrage, and the basis of the distance-vector routing protocol RIP.
• DAG shortest (or longest) path: relax edges in topological order, one pass, O(V + E) - works with negative weights, since a DAG has no cycles. Used for PERT/CPM project scheduling and critical paths.
• Floyd-Warshall (all pairs): dynamic programming over the set of permitted intermediate vertices. d_k[i][j] = min(d_{k−1}[i][j], d_{k−1}[i][k] + d_{k−1}[k][j]). Time Θ(V³), space Θ(V²) (the k loop must be the outermost loop). Handles negative edges; a negative d[i][i] after the run signals a negative cycle. With boolean OR/AND it becomes Warshall's transitive closure.
• Johnson's algorithm: reweight with Bellman-Ford potentials to remove negative edges, then run Dijkstra from every vertex - O(V·E + V·E log V), better than Floyd-Warshall on sparse graphs.
• Choosing: unweighted → BFS; all weights equal → BFS; weights 0/1 → 0-1 BFS; non-negative → Dijkstra; negative edges, one source → Bellman-Ford; DAG → topological relaxation; all pairs, dense → Floyd-Warshall; all pairs, sparse → Johnson.

Key points

• BFS - level-order traversal with a queue; O(V+E); gives the minimum edge-count shortest path.
• DFS - depth-first with a stack or recursion; O(V+E); gives timestamps, edge types and topological order.
• Mark visited on enqueue in BFS, else vertices duplicate in the queue.
• Adjacency list vs matrix - O(V+E) vs O(V²) traversal; matrix wins only for dense graphs and O(1) edge queries.
• Back edge ⟺ cycle - in both directed (grey vertex) and undirected (visited non-parent) graphs.
• Topological sort - reverse DFS finish order, or Kahn's in-degree BFS; exists iff the graph is a DAG; may be non-unique.
• Bipartite test - BFS 2-colouring; a graph is bipartite iff it has no odd-length cycle; an edge within a BFS level means not bipartite.
• Relaxation - d[v] = min(d[v], d[u] + w(u,v)); the single primitive of all shortest-path algorithms.
• Dijkstra - greedy, non-negative weights only, O(E log V) with a binary heap, O(V²) with an array.
• Bellman-Ford - V−1 passes over all edges, O(V·E), handles negative weights and detects negative cycles in the Vth pass.
• Floyd-Warshall - Θ(V³) all-pairs DP; k must be the outer loop; negative diagonal reveals a negative cycle.
• DAG relaxation - one pass in topological order, O(V+E), works for negative weights and longest paths.
• Negative cycle ⇒ shortest path is −∞ and undefined; shortest *simple* path becomes NP-hard.
• Sub-path optimality - every sub-path of a shortest path is shortest; the reason greedy and DP both apply.
• SCC - Kosaraju (two DFS passes + transpose) or Tarjan (low-link), both O(V+E); condensing SCCs yields a DAG.
• Articulation point / bridge - found by DFS low-link; a bridge (u,v) satisfies low[v] > d[u].
• Multi-source BFS - seed the queue with all sources at dist 0 to get the nearest-source distance everywhere.
• A\* - Dijkstra with an admissible heuristic; optimal and faster when the heuristic is informative.

Formulas and examples

Symbols: V, E = vertex and edge counts; w(u,v) = edge weight (cost, distance in km, time in minutes, fare in rupees); d[v] = current estimate; δ(s,v) = true shortest cost; π[v] = predecessor; C = maximum integer weight.

Example 1 - BFS, levels and bipartiteness. Undirected graph, 8 vertices, 9 edges: 1-2, 1-3, 2-4, 2-5, 3-6, 4-7, 5-7, 6-8, 7-8. BFS from vertex 1, neighbours in increasing order.

• Visit order 1, 2, 3, 4, 5, 6, 7, 8; dist = 1:0, 2:1, 3:1, 4:2, 5:2, 6:2, 7:3, 8:3.
• Levels: {1} | {2,3} | {4,5,6} | {7,8}. Tree edges = 7 (= n−1); non-tree edges = 5-7 and 7-8.
• Vertex 8 is at distance 3 via 1-3-6-8, not 4 via 1-2-4-7-8 - BFS always finds the minimum edge count.
• Edge 7-8 joins two vertices of the same level, so the graph contains an odd cycle (7-8-6-3-1-2-4-7, length 7) and is not bipartite.

Example 2 - DFS timestamps and edge classification. Directed graph: 1→2, 1→3, 2→4, 3→4, 4→5, 5→2, 5→6. DFS from 1, neighbours in increasing order, clock starting at 1.

• Tree edges: 1→2, 2→4, 4→5, 5→6, 1→3. Back edge: 5→2 (2 is grey when examined). Cross edge: 3→4 (f[4] = 8 < d[3] = 10, and 4 is not a descendant of 3).
• The back edge proves the cycle 2→4→5→2, so no topological order exists. (Adding 1→4 would create a forward edge, since 1's interval contains 4's interval.)
• Decreasing finish order 1, 3, 2, 4, 5, 6 would be the topological order if the cycle were removed.

Example 3 - Dijkstra from A. Undirected weighted graph (km): A-B 4, A-C 2, B-C 5, B-D 10, C-E 3, E-D 4, D-F 11.

Final distances: A 0, C 2, B 4, E 5, D 9, F 20 km. Shortest path to F = A-C-E-D-F = 2+3+4+11 = 20 km (the direct-looking A-B-D-F costs 4+10+11 = 25 km). Note D's estimate was improved after it had already been given a value - that is allowed; only finalised vertices never change.

Example 4 - Bellman-Ford with a negative edge. Directed graph, source 1. Edges relaxed in the fixed order (1,2)6, (1,3)7, (2,3)8, (2,4)5, (2,5)−4, (3,4)−3, (3,5)9, (4,2)−2, (5,1)2, (5,4)7.

• Pass 1 detail: d[2]=6, d[3]=7, d[4]=11 via (2,4), improved to 4 via (3,4) since 7−3 = 4, then d[2] improved to 2 via (4,2) since 4−2 = 2; d[5] = 6−4 = 2.
• Pass 2: (2,5) gives 2−4 = −2, improving d[5].
• Verification pass: no edge relaxes - for example (5,1) gives −2+2 = 0, equal to d[1], so no negative-weight cycle. Shortest path to 5 = 1→3→4→2→5 = 7−3−2−4 = −2. Dijkstra on this graph would wrongly finalise d[2] = 6 and return d[5] = 2.

Example 5 - Floyd-Warshall on 4 vertices. Directed: 1→2 = 3, 1→4 = 7, 2→1 = 8, 2→3 = 2, 3→1 = 5, 3→4 = 1, 4→1 = 2.

• k = 1: d[2][4] = 8+7 = 15; d[3][2] = 5+3 = 8; d[4][2] = 2+3 = 5.
• k = 2: d[1][3] = 3+2 = 5; d[4][3] = 5+2 = 7.
• k = 3: d[1][4] = 5+1 = 6; d[2][1] = 2+5 = 7; d[2][4] = 2+1 = 3.
• k = 4: d[2][1] = 3+2 = 5; d[3][1] = 1+2 = 3; d[3][2] = 1+5 = 6.

Checks: 3→1 = 3 via 3→4→1 (1+2), beating the direct edge 5; 3→2 = 6 via 3→4→1→2 (1+2+3); 4→3 = 7 via 4→1→2→3 (2+3+2). Diagonal stays 0 - no negative cycle.

Reference implementations

from collections import deque
import heapq

def bfs(adj, s, n):                      # unweighted shortest paths, O(V+E)
    dist = [-1] * n; dist[s] = 0
    q = deque([s])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:            # mark on enqueue
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

def dfs_iterative(adj, s, n):            # O(V+E), no recursion limit
    seen = [False] * n; st = [s]; order = []
    while st:
        u = st.pop()
        if seen[u]: continue
        seen[u] = True; order.append(u)
        for v in reversed(adj[u]): 
            if not seen[v]: st.append(v)
    return order

def dijkstra(adj, s, n):                 # adj[u] = [(v, w), ...], w >= 0
    INF = float('inf'); d = [INF] * n; d[s] = 0
    pq = [(0, s)]
    while pq:
        du, u = heapq.heappop(pq)
        if du > d[u]: continue           # stale entry
        for v, w in adj[u]:
            if du + w < d[v]:
                d[v] = du + w
                heapq.heappush(pq, (d[v], v))
    return d

def bellman_ford(edges, s, n):           # edges = [(u, v, w), ...]
    INF = float('inf'); d = [INF] * n; d[s] = 0
    for _ in range(n - 1):
        changed = False
        for u, v, w in edges:
            if d[u] != INF and d[u] + w < d[v]:
                d[v] = d[u] + w; changed = True
        if not changed: break
    for u, v, w in edges:                # Vth pass = detection
        if d[u] != INF and d[u] + w < d[v]:
            return None                  # negative-weight cycle
    return d

Where it is used

• Maps and navigation: Google Maps, MapmyIndia/Mappls, Ola, Uber and Rapido route on road graphs with Dijkstra/A* and contraction-hierarchy variants; edge weights are live travel times, not kilometres.
• Public transport planning: Delhi Metro, Namma Metro and Kochi Metro route planners, and IRCTC train-connectivity queries, are shortest-path or minimum-interchange problems on station graphs.
• Computer networks: OSPF and IS-IS run Dijkstra on the link-state database; RIP is a distance-vector (Bellman-Ford) protocol; IP forwarding tables are shortest-path trees - core material for network-engineer roles at Jio, Airtel, Cisco and Tata Communications.
• Logistics and delivery: Swiggy, Zomato, Zepto, Blinkit, Delhivery and Ecom Express use shortest-path cores inside fleet assignment and multi-drop routing; multi-source BFS finds the nearest dark store or hub.
• Software engineering tooling: topological sort resolves dependencies in Maven, Gradle, npm, Make and database migrations; DFS cycle detection flags circular imports and deadlock wait-for cycles; SCC analysis compresses call and module graphs.
• Data, social and finance: degrees-of-separation and friend recommendation on LinkedIn/Instagram graphs (BFS), fraud-ring detection via SCCs and connected components in UPI/NEFT transaction graphs at NPCI-facing fintechs, negative-cycle detection for arbitrage, and PERT/CPM critical-path scheduling in construction and infrastructure projects.

Interview questions

• Q: When does BFS give the shortest path and when does it fail? A: It gives the shortest path when all edges have equal weight (or the graph is unweighted); it fails on general weighted graphs because fewer edges can still cost more.
• Q: Why does Dijkstra's algorithm fail with negative edge weights? A: Its greedy invariant assumes that once a vertex is extracted with the smallest estimate no later path can improve it; a negative edge can reduce the cost of an already finalised vertex, so the proof and the answer break.
• Q: How does Bellman-Ford detect a negative-weight cycle? A: Any shortest path uses at most V−1 edges, so after V−1 passes nothing should improve; if a Vth pass still relaxes some edge, a negative cycle is reachable from the source.
• Q: How do you detect a cycle in a directed graph in O(V+E)? A: DFS with three colours - an edge to a grey (on-stack) vertex is a back edge and proves a cycle; alternatively run Kahn's algorithm and check whether fewer than V vertices are output.
• Q: Why can't a DFS on an undirected graph have cross edges? A: If an edge (u,v) existed with v already finished and unrelated to u, then v's DFS would have explored the same edge back to u and discovered u first - so u and v must be ancestor-descendant.
• Q: What is the time complexity of Dijkstra, and when is the O(V²) version better? A: O((V+E) log V) with a binary heap; the array version at O(V²) is better for dense graphs where E ≈ V², since V² beats V² log V.
• Q: Why must k be the outermost loop in Floyd-Warshall? A: k is the DP stage - the set of allowed intermediate vertices. Putting it inside would mix stages and compute wrong values for some pairs.
• Q: How do you find the shortest path in a DAG with negative edge weights? A: Topologically sort the DAG and relax edges once in that order - O(V+E); negating weights gives the longest path, which is also solvable only because there are no cycles.
• Q: How do you reconstruct the actual path, not just its cost? A: Store a predecessor array during relaxation and walk back from the destination to the source, then reverse it; Floyd-Warshall stores a next/parent matrix instead.
• Q: How would you find the shortest path when weights are only 0 and 1? A: 0-1 BFS with a deque - push-front on a 0-weight edge and push-back on a 1-weight edge, giving O(V+E) instead of O(E log V).
• Q: Given a 1,000 × 1,000 grid and 50 exits, how do you get each cell's distance to the nearest exit? A: Multi-source BFS - enqueue all 50 exits with distance 0 and run one BFS, O(number of cells).
• Q: What is the difference between Kosaraju's and Tarjan's SCC algorithms? A: Both are O(V+E); Kosaraju does two DFS passes and needs the transposed graph, Tarjan does a single DFS using discovery and low-link values with a stack.

Common mistakes

• Marking a vertex visited when it is dequeued instead of when it is enqueued - the same vertex enters the BFS queue repeatedly and the complexity degrades.
• Using BFS or DFS for shortest paths on a weighted graph; DFS never gives shortest paths even when the graph is unweighted.
• Running Dijkstra on a graph with negative edges, or "fixing" it by adding a constant to every weight - that changes which path is cheapest, because paths have different edge counts.
• In Floyd-Warshall, writing the loops as i, j, k, or initialising non-edges to a large number that overflows when two are added (use a sentinel and guard before adding).
• Forgetting that an undirected edge must be inserted into both adjacency lists, and that the undirected traversal scans 2E entries.
• Running BFS/DFS from a single source and declaring the whole graph traversed - a disconnected graph needs a loop over all vertices, and a directed graph may simply not reach everything.
• Relying on deep recursion for DFS on large graphs (Python's default limit is about 1,000 frames) instead of an iterative stack, and confusing "visited" with "currently on the stack" in directed cycle detection.

Related topics

Minimum spanning trees and network flow · Dynamic programming · Greedy algorithms · Time and space complexity · DSA interview patterns · Recursion and backtracking