Choose hops or cost before choosing a path algorithm

Clarify the observable contract

The question shortest path is incomplete until the objective is specified. BFS minimizes edge count when each traversed edge contributes the same unit cost. In this counterexample a direct edge has one hop but cost ten, while a two-edge path costs one plus one. The program demonstrates the disagreement rather than presenting another full weighted shortest-path implementation.

Ask whether every edge represents the same unit, whether costs may be negative and whether the caller wants a distance or an actual path. Those answers determine both the algorithm and the return contract. A route with fewer transitions is not necessarily cheaper, faster or safer unless the chosen metric says so.

Walk through the verified program

BFS enqueues T and A from S and reaches T at one hop. The separate cost calculations show ten for the direct route and two through A. Those weighted values are explicit fixture facts, not costs discovered by BFS. The graph is finite, includes an adjacency entry for every node and uses exact ordinal node names.

Marking a node seen when it is enqueued avoids repeated BFS expansion and preserves the first-discovered minimum hop count for unit edges. The explicit weighted arithmetic below the traversal is a counterexample to changing metrics without changing the algorithm. It should never be presented as a weighted distance computed by that queue.

using System;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Text;

var graph=new Dictionary<string,string[]>(StringComparer.Ordinal) { ["S"]=new[]{"T","A"}, ["A"]=new[]{"T"}, ["T"]=Array.Empty<string>() };
var queue=new Queue<(string Node,int Hops)>(); var seen=new HashSet<string>(StringComparer.Ordinal){"S"}; queue.Enqueue(("S",0));
int hops=-1; while(queue.Count>0) { var item=queue.Dequeue(); if(item.Node=="T") { hops=item.Hops; break; } foreach(string next in graph[item.Node]) if(seen.Add(next)) queue.Enqueue((next,item.Hops+1)); }
Console.WriteLine("fewest hops:"+hops);
Console.WriteLine("direct cost:"+10);
Console.WriteLine("via A cost:"+(1+1));

Account for time, storage and allocations

BFS uses O(V+E) time and O(V) discovered-state storage for the reachable graph, assuming ordinary set operations. Nonnegative weighted costs require an appropriate weighted algorithm such as Dijkstra; negative edges require different assumptions. No priority queue can repair a missing definition of the path objective.

The V-plus-E bound describes the reachable adjacency representation, not arbitrary network exploration. Storing predecessor links would add another O(V) structure but allow reconstruction of a path. Weighted accumulated costs also need a numeric bound and overflow policy beyond the integer hop count of this tiny graph.

Review assumptions and likely defects

Adding weights to an input record while retaining first-discovery BFS distances does not preserve minimum-total-cost correctness. Reusing the word shortest for both outputs conceals that contract change. The example also does not validate dangling adjacency names or handle an unbounded externally supplied graph.

Tie handling matters once the return value includes a route. Neighbor order can decide which equal-hop path BFS discovers first. If the product requires lexicographically smallest paths or another deterministic rule, the representation and traversal order must enforce it rather than inheriting incidental dictionary or input ordering.

Practice one: discriminate edge cases

Change the direct cost to two and explain the remaining tie between one-hop and two-hop routes. Hint: equal total cost still leaves an output tie policy if the API returns a path rather than only a distance.

Add another two-edge path with the same total cost and a different intermediate node. State whether either route is acceptable or whether an explicit tie breaker applies. Keep the cost-equality question separate from the hop-count disagreement so the test does not accidentally change two requirements at once.

Practice two: defend an extension

Design a route API that exposes its metric, unreachable result and tie policy. State whether negative weights are valid and how overflow of accumulated cost is handled. Refer to the existing algorithms course for Dijkstra mechanics instead of duplicating it here.

A route API can declare metric kind, reject unsupported negative weights and return a named unreachable outcome rather than a magic numeric distance. For actual path results, retain predecessors and specify tie ordering. Dijkstra can serve nonnegative weighted distance under its usual assumptions; selecting it does not excuse missing validation or overflow handling.

Evaluate correctness and interview reasoning

The interview value is recognizing an underspecified objective before implementing another familiar algorithm. The sample reuses BFS mechanics only to construct a concrete disagreement: one hop costs ten, while two hops cost two. A correct explanation labels both quantities and never attributes the weighted result to BFS. A senior answer then asks about negative edges, unreachable nodes, cost accumulation and path ties. Those contract choices are prerequisites to a useful implementation. Existing weighted-algorithm lessons provide mechanics once the problem has actually selected the metric they solve.