Algorithms · Cluster
Shortest Paths
Path costs, relaxation, and all-pairs methods.
- 01 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.
- 02 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.
- 03 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.
- 04 Priority Queues for Dijkstra: Decrease-Key, Lazy Deletion, and Buckets The four practical queue designs behind the same greedy loop, what each costs per operation, and how integer weight bounds turn a comparison heap into an array of buckets.
- 05 A* and the Conditions on a Heuristic Admissibility versus consistency, why a consistent heuristic removes the need to reopen closed nodes, and what weighting the heuristic buys and costs in solution quality.
- 06 Bidirectional Search and the Problem of Knowing When to Stop Why two frontiers can meet without the answer being final, which stopping rules are provably safe, and how the meeting point is recovered from two label arrays.
- 07 Floyd-Warshall, Johnson Reweighting, and the All-Pairs Choice Two all-pairs methods with opposite preconditions: one tolerates negative edges through a triple loop, the other restores nonnegativity by changing the weights and then runs Dijkstra from every vertex.
- 08 Contraction Hierarchies and Preprocessing for Road Networks How contracting vertices in a fixed order adds shortcut edges that preserve all distances, and why a bidirectional search that only moves upward then answers queries with a small fraction of the work.
- 09 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.
- 10 Resource-Constrained Shortest Paths and Label-Setting with Dominance Why a second additive cost breaks the optimal-substructure argument, how multi-dimensional labels and a dominance rule restore a workable search, and what makes the label count explode.