Tag
graph-algorithms
- Jul 8, 2026 Bellman-Ford, Round Counts, and Negative-Cycle Detection Why |V|-1 passes suffice, what the extra pass detects, how queue-driven label correction changes the cost without changing the answer, and why detection is easier than extracting the cycle. algorithms
- Sep 27, 2025 Dijkstra and the Settled-Set Invariant Why extracting the minimum tentative label is safe only when weights are nonnegative, how the exchange argument proves it, and what a settled set costs in memory and bookkeeping. algorithms
- Aug 29, 2025 Relaxation and the Optimality Condition Behind Shortest-Path Algorithms How one comparison operation encodes the shortest-path optimality condition, why the schedule of relaxations determines which algorithm results, and what happens when the answer is unbounded below. algorithms
- Jan 17, 2025 Minimum Mean Cycle and the Shape of Negative-Weight Answers How to find the cycle with the smallest weight per edge when every cycle has negative total weight, why the answer is a ratio rather than a sum, and how a parametric search reduces it to negative-cycle detection. algorithms