Phase 1: BFS gives wrong answer on weighted graph

The Weight-Blind Navigator

I used BFS on a weighted graph in an interview once. It gave the wrong answer. I did not even realize it was wrong until the interviewer asked me to trace the execution. That was the day I learned that BFS has a hidden assumption: all edges cost the same.

This graph has 4 nodes and 4 directed edges, each with a travel time (weight). The source is node 1. We want the MAXIMUM of all shortest distances — the last node to receive the signal. Run BFS on it and watch what happens.

FIG. 1 — WEIGHTED GRAPH — BFS WILL IGNORE THE WEIGHTS
BFS level: 0|BFS answer: ?|Correct answer: 6