GRAPH THEORY FOR COMPETITIVE PROGRAMMERS: WHEN TO USE WHICH ALGORITHM

Graph problems are everywhere in competitive programming — and the biggest mistake beginners make is not implementing algorithms wrong, it is choosing the wrong algorithm. Each has a specific domain where it is optimal and edge cases where it silently fails.

BFS — Unweighted Shortest Path

BFS is the correct choice when all edge weights are equal (or effectively 1). It is O(V + E) and guarantees the shortest path in number of edges. Use it for: grid problems with uniform movement cost, word ladders, level-order traversal, any minimum-steps problem. Common mistake: using BFS on a weighted graph. It finds minimum-hop paths, not minimum-cost paths.

Dijkstra — Non-Negative Weighted Shortest Path

Dijkstra is the standard for weighted shortest path when all edge weights are >= 0. With a binary heap it is O((V + E) log V). Critical constraint: Dijkstra is incorrect with negative edges. If a problem has negative weights, it is probably not Dijkstra.

import heapq
def dijkstra(graph, start):
    dist = {start: 0}
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float('inf')): continue
        for v, w in graph[u]:
            nd = dist[u] + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

Bellman-Ford — Negative Weights and Cycle Detection

Bellman-Ford handles negative edge weights and can detect negative cycles. It is O(V*E) — much slower. Use it when: the problem has negative weights, you need to detect negative cycles (currency arbitrage, etc.), or edges have constraints making Dijkstra incorrect. Run V-1 iterations to find shortest paths; if distances still update on the Vth iteration, there is a negative cycle.

Floyd-Warshall — All Pairs Shortest Path

Floyd-Warshall computes shortest paths between all pairs of vertices in O(V^3). Use it when V is small (typically under 400), you need all-pairs distances, or the problem asks about reachability between all pairs. DP recurrence: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) for each intermediate vertex k.

A* — Heuristic-Guided Single-Target Search

A* is Dijkstra with an admissible heuristic h(n) estimating cost from n to the goal. If h never overestimates, A* is optimal and typically much faster than Dijkstra for single-target queries. In my A*/Dijkstra paper, A* reduced node exploration by 78.13% on the Lucknow road network because geographic distance (Haversine) is an excellent admissible heuristic for road graphs.

The Decision Tree

Unweighted graph → BFS. Weighted, non-negative, single source → Dijkstra. Negative weights or cycle detection → Bellman-Ford. All pairs, small V → Floyd-Warshall. Single target, geometric graph → A*.

Subtleties That Cost Points

Integer overflow: edge weights summing above 2^31 require long long. Not initialising distances to infinity properly. Using BFS on a weighted graph and getting wrong answers on test cases with unequal weights. Forgetting Dijkstra is wrong on negative weights — if you get WA on what looks like a Dijkstra problem, check for hidden negative weights. I am preparing for IOI where graph problems are a core component. The implementation details matter as much as knowing which algorithm to choose.