Advanced Graphs
Retrieval: which graph algorithm?
Two problems rebuilt cold, plus the preconditions that pick the algorithm for you.
Key idea
Read the constraints, not the story
Every choice in this unit is forced by a precondition stated in the problem. Find the precondition and the algorithm follows.
| Situation | Use | Because |
|---|---|---|
| Unweighted, fewest steps | breadth-first search | equal edges make first arrival cheapest |
| Non-negative weights, cheapest path | heap-based greedy | popping finalizes, nothing can improve it |
| Negative weights, or a cap on edges used | relaxation in rounds | finalization is not valid |
| Connect everything at least total cost | spanning tree | not a path problem at all |
| Use every edge exactly once | record on dead end, reverse | greedy forward walk can strand |
Tip
And the meta-skill
Two of this unit's problems hide the graph. When a problem has no explicit edges but describes constraints, ordering, or transformations, write down what a node is and what an edge means before anything else.
Which algorithm?
Flights between cities have prices, some routes offer a rebate making the effective price negative, and you need the cheapest total from one city to another. Which approach is correct?
Network Delay Time, from scratch
You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.
Course Schedule II, from scratch
You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.