BFS, DFS, topological sort, shortest paths, and union-find, including spotting a graph problem in disguise.
6 questions in Data Structures & Algorithms.
Plain Dijkstra minimises cost alone, so it can return a cheap route with too many stops, and settling each city once discards a dearer route that still has stops to spare. Make the state city plus edges used, or run Bellman-Ford for exactly K + 1 rounds, each reading only the previous round's distances.
For one grid, number of islands is a flood fill: each unvisited land cell starts a BFS or DFS, O(rows x cols). For land arriving cell by cell, rerunning that is too slow, so use union-find. Each new cell adds one island, and each union with a neighbour in a different set removes one, at near-constant amortised cost.
Choose BFS when the question asks for the fewest steps in an unweighted graph or when you need results in distance order; choose DFS when you are asking a structural question such as connectivity, cycles or topological order, or when the graph is deep and narrow.
Dijkstra fails with negative edges because it finalises the current cheapest node under the assumption that no later edge can reduce it. Use Bellman-Ford when negative edges are possible, and reject graphs with negative cycles. It also connects shortest paths to the point an interviewer is testing.
Topological sort produces an order only for a directed acyclic graph. Kahn's algorithm removes zero-in-degree nodes and detects a cycle when fewer than all nodes are emitted; DFS detects a cycle with a back edge into the active stack. Use this GRAPHS answer to show the decision, trade-off, and evidence rather than a memorised definition.
You stop on four conditions and the success check has to come first, before bounds or character comparison. Revisiting is prevented per path rather than globally: a cell is marked when the search enters it and unmarked when the search leaves it, because a cell that ruins one candidate path has to remain available to a different one.