Weighted Graphs: Dijkstra and BFS

The problem

Some graph questions feel harmless until the phrase “shortest path” shows up.

Then a lot of people grab the first tool they remember:

• BFS
• Dijkstra

and hope it fits.

The problem is that they do not solve exactly the same thing.

Both traverse graphs.

But the kind of distance each one respects is different.

Mental model

BFS thinks in layers.

It is great when moving from one node to another always costs the same.

Dijkstra thinks in accumulated cost.

It is great when each edge can cost something different, as long as the weights are not negative.

In one short sentence:

BFS minimizes steps. Dijkstra minimizes cost.

If steps and cost are the same thing, BFS is enough.

If they are not, BFS stops being reliable.

Breaking it down

Question 1: what does “distance” mean here?

This is the question that saves the solution.

Distance can mean:

• number of edges
• total time
• total cost
• total risk
• total energy

If the interview says “fewest hops” and every hop costs the same, BFS usually works.

If it says “total cost” and each edge can charge a different amount, you are out of pure BFS territory.

When BFS works

BFS is perfect when:

• the graph is unweighted
• or all weights are equal

Why?

Because exploring level by level preserves the smallest number of steps.

The first time you reach a node, you reached it through the path with the fewest edges.

When Dijkstra comes in

If one edge can cost 1 and another can cost 100, “arriving first” no longer means “arriving cheaper.”

Now you need to keep expanding the next state with the lowest accumulated cost so far.

That is what the priority queue does.

It does not ask, “who got here first?”

It asks:

Which path is cheapest right now?

Negative weights change the game

Dijkstra assumes non-negative weights.

If negative weights exist, the idea that “the current lowest cost is safe to expand now” stops being true.

In an interview, just asking that early already shows maturity.

Simple example

Imagine this graph:

• A -> B with cost 100
• A -> C with cost 1
• C -> B with cost 1

If the question is “which path uses fewer edges?”, A -> B wins with one step.

If the question is “which path has the lowest total cost?”, A -> C -> B wins with cost 2.

This example clears up the confusion fast.

BFS would look at layers and find B early.

Dijkstra would look at accumulated cost and prefer going through C.

The role of the data structure

BFS

It usually uses:

• queue
• visited

You explore in order of arrival by layers.

Dijkstra

It usually uses:

• a distance map
• a priority queue or min-heap

You may even see the same node more than once in the queue with different costs.

The important part is to keep the smallest valid cost.

A classic mistake is marking a node as visited too early in Dijkstra, as if it were BFS.

In general, the safe moment to consider a node closed is when it comes out of the min-heap with the smallest known cost.

Common mistakes

• Using BFS on a weighted graph just because you want the “shortest path.”
• Forgetting that BFS minimizes hops, not weight.
• Using Dijkstra with negative weights.
• Marking a node as resolved too early in Dijkstra.
• Treating a plain queue and a min-heap as a cosmetic difference.

How a senior thinks

People who have seen this kind of question usually make the cut very early:

• is the cost uniform or variable?
• do I want the fewest steps or the lowest total weight?
• are negative weights possible?

Notice that this matters more than remembering the full pseudocode on the spot.

If you choose the right family of solution, the rest gets much less chaotic.

If you choose the wrong one, you can write beautiful code all day and the answer will still be off.

What the interviewer wants to see

The interviewer wants to see whether you:

• understand what the problem is minimizing
• can separate layers from accumulated cost
• know when BFS is enough
• know the limits of Dijkstra

A strong answer usually starts like this:

“Before choosing BFS or Dijkstra, I want to confirm whether all edges have the same cost and whether negative weights exist.”

That already shows you are not choosing by reflex.

In graphs, “shortest path” means nothing until you define the metric.

When the cost changes, the order of exploration has to change too.