Dijkstra vs. BFS: When the Cheapest Path Has More Edges

By Hourly DSA · October 4, 2026 · 4 min read

BFS finds paths with the fewest edges; Dijkstra's algorithm finds minimum-total-weight paths when edge weights are nonnegative. Those objectives agree for equal positive edge weights, but they can disagree as soon as costs vary.

Before choosing a traversal, clarify what the word “shortest” measures.

Fewer edges can cost more

Consider these directed connections:

A → B costs 8
A → C costs 2
C → B costs 1

The direct route A→B uses one edge and costs 8. The route A→C→B uses two edges and costs 3.

BFS discovers B directly from A. That is correct if you're minimizing the number of hops, but it does not establish the cheapest weighted route.

Dijkstra prioritizes the smallest known total cost rather than the oldest discovered vertex.

Store the best distance known so far

Set A's distance to zero and the others to infinity. Put A in a min-heap keyed by distance.

When processing a vertex, try extending its current path along each outgoing edge. If the resulting cost improves a neighbor's stored distance, update that distance and add the new candidate to the heap.

This operation is called relaxation. It asks whether going through the current vertex gives a cheaper route than anything found so far.

For our graph:

Remove A at cost 0. Discover B at 8 and C at 2.
Remove C at cost 2. Its edge to B gives 2 + 1 = 3, improving B from 8 to 3.
Remove B at cost 3. Its minimum distance is now settled.

The heap still may contain the older candidate for B at cost 8. That entry no longer matches B's best distance, so skip it when it is removed.

Discovery does not mean finished

Marking B permanently visited when it first enters the heap would freeze the wrong answer, 8.

With nonnegative weights, a vertex can be settled when its current smallest-distance entry is removed from the min-heap. Any route through a still-unsettled vertex cannot later produce a cheaper distance: it starts from a distance at least as large and adds no negative cost.

That is the greedy argument behind Dijkstra. The priority queue helps enforce the ordering, but the nonnegative-weight assumption makes the ordering safe.

If you only need one destination, you may stop when that destination is settled. Stopping when it is first discovered is too early.

Why negative weights change the argument

Change the graph to A→B with cost 2, A→C with cost 5, and C→B with cost −4.

The cheapest route to B now costs 1 through C. Yet a standard Dijkstra run settles B at 2 before processing C at 5.

A later negative edge can overturn the earlier decision. The graph does not even need a negative cycle to break that finalization rule. Algorithms such as Bellman–Ford handle negative edges under different assumptions and costs.

Zero-weight edges are fine; the requirement is nonnegative, not strictly positive.

Account for the heap implementation

An indexed binary heap with decrease-key supports O((V + E) log V) time and O(V) auxiliary storage, apart from the graph.

A simpler implementation inserts a new entry after each improvement and skips stale entries later. It can store O(E) heap entries and takes O(V + E log(E + 1)) time. For simple connected graphs, this is commonly expressed as O((V + E) log V).

Use the bound that matches the implementation rather than assuming all priority queues behave identically.

Choose the right notion of distance

If every edge costs 1, is Dijkstra necessary?

No. BFS already explores vertices in increasing total cost because each additional edge adds exactly one. It runs in O(V + E) time with adjacency lists.

Practice naming the quantity being minimized before choosing a data structure. Hourly DSA turns that kind of approach selection into a short reasoning exercise.