Tag
shortest-paths
- Oct 7, 2026 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. 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
- Jan 31, 2026 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. algorithms
- Oct 30, 2025 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. 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
- Dec 3, 2024 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. algorithms
- Aug 22, 2024 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. algorithms
- Apr 8, 2024 Why Breadth-First Search Cannot Discover Vertices Out of Distance Order The queue invariant behind BFS distances, why vertices must be marked on enqueue rather than on dequeue, and where the layer argument stops holding. algorithms
- Aug 24, 2023 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. algorithms