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

Quick check· 5 min

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?

Relaxation in rounds, because the greedy finalization argument fails with negative edgesThe heap-based greedy algorithm, since it handles any weightsBreadth-first search, counting flights rather than priceA minimum spanning tree over the flight network

Problem· 20 min

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.

Problem· 18 min

Course Schedule II, from scratch

Advanced Graphs

121 / 170

Advanced GraphsLesson 6 of 6About 48 min

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

Quick check· 5 min

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?

Problem· 20 min

Network Delay Time, from scratch

Problem· 18 min