Course contentsShow
← Computer Science
Lesson 976 of 2,87223. Shortest Path AlgorithmsFree lesson

Dijkstra's on Dense vs Sparse Graphs

Analyzing when array-based O(V²) is better than heap-based O((V + E) log V) implementations.

Dijkstra's on Dense vs Sparse Graphs

You'll learn when to choose the simpler array-based Dijkstra's over the more complex heap-based version.

The Core Tradeoff

Dijkstra's algorithm can be implemented two ways, and each shines in different scenarios:

  1. Array-based (simple priority queue): O(V²) time complexity
  2. Binary heap-based: O((V + E) log V) time complexity

The key question: which is actually faster for your graph?

Dense Graphs Favor Arrays

A dense graph has many edges—close to V² edges (think a social network where almost everyone knows everyone). Here:

  • The array version does V² work regardless of edges
  • The heap version does approximately (V² + V²) log V = O(V² log V) work
  • Array wins: O(V²) < O(V² log V)

The simpler code is also faster! No heap operations, just scan an array V times.

Sparse Graphs Favor Heaps

A sparse graph has few edges—closer to V edges (think a road network). Here:

  • The array version still does V² work (unchanged)
  • The heap version does approximately (V + V) log V = O(V log V) work
  • Heap wins: O(V log V) < O(V²)

The extra complexity of maintaining a heap pays off when you're not examining many edges.

The Practical Rule

Use array-based when E ≈ V² (dense), and heap-based when E ≈ V (sparse). The breakeven point is roughly when E = V²/log V, but in practice, if your graph has more than about V log V edges, consider the simpler array approach.

Key Takeaway: For dense graphs (many edges), the O(V²) array implementation beats the O((V + E) log V) heap version; for sparse graphs (few edges), the heap's logarithmic advantage wins.