Choosing between BFS, DFS, Dijkstra and DP

A strong candidate reframes the question: each of these answers a specific question about a specific kind of graph. What am I being asked — reachability, a shortest path, an ordering, an optimal value — and what does the graph look like — weighted or not, cyclic or not, explicit or implicit (states in a puzzle are a graph too).

Breadth-First Search (BFS) answers "fewest edges" and explores by distance layers; it is optimal only when every edge costs the same. Depth-First Search (DFS) answers structural questions — does a path exist, are there cycles, what is a topological order, which components exist — and is the natural backbone of backtracking. Dijkstra's Algorithm is BFS generalized to non-negative weights: replace the queue with a Priority Queue and you are done; its correctness argument breaks the moment a negative edge appears. Dynamic Programming is shortest (or best) path on a DAG: the subproblem dependency graph must be acyclic so subproblems can be solved in one topological pass.

The unifying view: all four are "process states in a valid order and relax transitions". BFS orders by hop count, Dijkstra by tentative distance, DP by topological order of subproblems, DFS by discovery. If the state graph has cycles and weights, you cannot use DP and need Dijkstra; if it is acyclic, DP is simpler and linear; if weights are uniform, BFS is both simpler and faster than Dijkstra.