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
| Operation | Cost |
|---|---|
| BFS (unweighted) | O(V + E) |
| Dijkstra with binary heap | O((V + E) log V) |
| Bellman-Ford | O(V · E) |
| Floyd-Warshall | O(V³) time, O(V²) space |
| Prim / Kruskal MST | O(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
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
vector<long long> dijkstra(int n, const vector<array<int, 3>>& edges, int source) {
vector<vector<pair<int, int>>> graph(n);
for (auto& e : edges) graph[e[0]].push_back({e[1], e[2]});
const long long INF = LLONG_MAX / 4;
vector<long long> dist(n, INF);
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> heap;
dist[source] = 0;
heap.push({0, source});
while (!heap.empty()) {
auto [d, u] = heap.top(); heap.pop();
if (d > dist[u]) continue; // stale entry
for (auto [v, w] : graph[u])
if (d + w < dist[v]) {
dist[v] = d + w;
heap.push({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.
-
Dijkstra's algorithm gives wrong answers when the graph has:
It assumes a vertex popped from the heap is final, which a later negative edge can break.
-
Dijkstra with a binary heap runs in about:
Each edge can cause one heap push, and each heap operation costs log V.
-
Which algorithm handles negative weights and detects negative cycles?
It relaxes every edge V - 1 times; an improvement on one more pass means a negative cycle.
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.
- Network Delay TimeLeetCode Medium +40
- Shortest Path in Binary MatrixLeetCode Medium +40
- Path With Minimum EffortLeetCode Medium +40
- Cheapest Flights Within K StopsLeetCode Medium +40
- Find the City With the Smallest Number of Neighbors at a Threshold DistanceLeetCode Medium +40
- Min Cost to Connect All PointsLeetCode Medium +40
- Swim in Rising WaterLeetCode Hard +70
Stuck on Shortest Paths?Ask Orbi for a hint, a fresh explanation or a review of your code.
Ask the tutor