Overview

Once edges have weights, BFS no longer finds shortest paths. Dijkstra's algorithm generalises it: instead of a plain queue it uses a min-heap keyed by distance, always settling the closest unsettled vertex next. It is correct as long as no edge weight is negative, and it runs in O((V + E) log V).

Other situations call for other tools. Bellman-Ford tolerates negative edges, detects negative cycles and naturally limits paths to k edges. Floyd-Warshall computes all-pairs distances in O(V³) for small graphs. And when the goal is not a path but the cheapest set of edges connecting every vertex — a minimum spanning tree — Prim's (heap-based) or Kruskal's (Union-Find-based) algorithm applies.

Key concepts

Tick a concept once you can explain it in your own words without notes.

Complexity cheat sheet

OperationCost
BFS (unweighted)O(V + E)
Dijkstra with binary heapO((V + E) log V)
Bellman-FordO(V · E)
Floyd-WarshallO(V³) time, O(V²) space
Prim / Kruskal MSTO(E log V) / O(E log E)

Patterns to recognise

Single-source, non-negative

Use it for: Network delay time, path with minimum effort.

Dijkstra; the "distance" can be any monotone cost, such as the maximum step so far.

At most k edges

Use it for: Cheapest flights within k stops.

Bellman-Ford for k + 1 rounds, copying the distance array each round.

Connect everything cheaply

Use it for: Min cost to connect all points.

Kruskal with Union-Find, or Prim with a heap on dense graphs.

Code template

Dijkstra's algorithm with a min-heap
import heapq


def dijkstra(n, edges, source):
    graph = [[] for _ in range(n)]
    for u, v, w in edges:
        graph[u].append((v, w))
    dist = [float('inf')] * n
    dist[source] = 0
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                         # stale entry
        for v, w in graph[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))
    return dist

Common mistakes

  • Dijkstra gives wrong answers with negative edge weights.
  • Forgetting to skip stale heap entries makes Dijkstra much slower.
  • Using INT_MAX as infinity and then adding a weight overflows; use a large but safe sentinel.
  • Problems often number vertices from 1 — size arrays accordingly.

Quick check

Three questions on Shortest Paths. Get all three right to earn +15 XP.

  1. Dijkstra's algorithm gives wrong answers when the graph has:

  2. Dijkstra with a binary heap runs in about:

  3. Which algorithm handles negative weights and detects negative cycles?

Challenges

Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.

Stuck on Shortest Paths?Ask Orbi for a hint, a fresh explanation or a review of your code.

Ask the tutor