Graph Theory37 sections · 1633 units
Open in Course

Common Mistakes

(What to avoid)

Forgetting to run the nn-th iteration means you cannot detect negative cycles. Always run one extra iteration after the n1n-1 standard iterations. Using single-array relaxation in constrained problems (like Cheapest Flights) allows paths longer than intended.

Always use two arrays when controlling path length. Not tracking parent pointers makes cycle reconstruction impossible. Always store parents if you need to output the cycle, not detect it. Parent tracking is required for path reconstruction.