A good way to think about Dijkstra is:

Dijkstra works when the first time you remove a node from the priority queue, you already know its optimal value.

This is called the greedy property.

If a node's value can still improve later by taking a different path, Dijkstra is not applicable.

---

Cases where Dijkstra works

1. Shortest Path (Classic)

Edges represent distances.

Suppose we're finding the shortest path from A.

Initially 

We pop B first because 2 < 5.

Could there later be another path to B shorter than 2?

No.

Any other path must go through C, whose distance is already ≥5.

So

Impossible to improve.

This is exactly why Dijkstra works.

Requirement:

• edge weights ≥ 0

---

2. Network Latency

Total latency

Again,

• weights are nonnegative
• costs only increase

Perfect for Dijkstra.

---

3. GPS Navigation

Road lengths

Distance always accumulates positively.

Works.

---

4. Cheapest Flight (without discounts)

Edge

Cost

Again additive positive cost.

Works.

---

5. Maximum Bottleneck Path (modified Dijkstra)

Suppose bandwidths

Path capacity is

So

We maximize the minimum.

A modified Dijkstra works because

The capacity never increases after extending a path.

The greedy property still holds.

---

Cases where Dijkstra does NOT work

1. Negative Edges

Initially

Dijkstra pops

But later

Much better.

Too late.

Greedy fails.

Bellman-Ford is needed.

---

2. Currency Exchange (your problem)

Products 

vs

Notice

looked optimal initially

but later became

Dijkstra finalized B too early.

---

3. Longest Path

Suppose 

Longest path

vs

Again

looked finished

but wasn't.

---

4. Maximum Product

Exactly your interview problem.

Products may increase dramatically later.

Greedy property breaks.

---

5. Paths with Rewards

Imagine

Objective

Reaching a node cheaply isn't necessarily best if another path collects much more reward.

No greedy property.

---

A useful rule of thumb

Suppose your path value is

Ask:

Can extending a worse path ever make it better than a currently better path?

If the answer is No, Dijkstra usually works.

If Yes, Dijkstra usually fails.

---

Works

Sum

with

Cannot decrease.

Works.

---

Minimum

Cannot increase.

Works.

---

Maximum

Cannot decrease in the relevant direction.

Works.

---

Doesn't work

Product

because

A worse partial product

can become

while the better one

becomes

Ordering changes.

---

Sum with negative edges

A worse partial sum can become better.

Ordering changes.

---

Interview heuristic

When solving a graph problem, ask these questions:

1. Is the objective additive?
   • distance += edge
   • cost += edge
   • time += edge
   • → Think Dijkstra.
2. Are all edge "increments" non-negative?
   • If not, Dijkstra is unsafe.
3. Can the ranking of two partial paths flip after extending them?

For example, suppose two paths reach different nodes with current values:

If after one more edge you can get:

then the ordering has flipped. Once this can happen, the greedy assumption behind Dijkstra no longer holds, and you should be suspicious of using it.

This "can the ordering flip?" test is one of the quickest ways to judge whether Dijkstra is appropriate in an interview.