Dijkstra shortest path
Permanently settle the smallest tentative distance; nonnegative weights ensure that label can never improve later.
Complexity. O((|V|+|E|) log |V|)
Read the complete articleRESEARCH BLOG · ALGORITHM BY ALGORITHM
A rigorous reading path through every algorithm in the current public Python release. Each entry states the mathematical problem, the operative idea, the procedure, the certificate, the computational limit and the exact source file.
Research Blog & Public Algorithm Atlas
Connected components
One traversal from an unseen seed discovers exactly one component.
Complexity. O(|V|+|E|)
Read the complete articleKruskal minimum spanning tree
Accept the lightest edge that joins different components.
Complexity. O(|E| log |E|)
Read the complete articleHungarian assignment
Dual potentials expose zero reduced-cost augmenting assignments.
Complexity. O(n³) after padding
Read the complete articleTSP assignment relaxation
Every tour is a cycle cover, while a cycle cover may contain several cycles.
Complexity. O(n³)
Read the complete articleCycle contraction and patching
Enumerate cycle order and entry points while measuring bridge deltas exactly.
Complexity. Exponential in cycle count and entry choices
Read the complete articleCycle branch and bound
A lower bound on unfinished bridge cost prunes partial reconnections.
Complexity. Exponential in the worst case
Read the complete articleBinary branch and bound
LP relaxations bound subtrees; fractional variables split the search.
Complexity. Exponential in the worst case
Read the complete articleBranch and cut
Remove fractional LP points without removing integer-feasible solutions.
Complexity. Problem-dependent; exponential worst case
Read the complete articleHeld-Karp subset dynamic programming
The best partial tour is identified by visited subset and final vertex.
Complexity. O(2ⁿn²) time; O(2ⁿn) memory
Read the complete articleOne-tree lower bound
Combine an MST excluding the depot with its two cheapest incident edges.
Complexity. O(n²) in the dense implementation
Read the complete articleNearest neighbour + 2-opt
Build greedily, then reverse segments that reduce two-edge cost.
Complexity. O(n³) in the simple implementation
Read the complete articleSynchronization-state exact DP
A state needs the served mask and the common synchronization node.
Complexity. Exponential subset DP
Read the complete articleWeighted-interval sortie DP
Take-or-skip recurrence over intervals ordered by rendezvous position.
Complexity. O(m²) with direct predecessor search
Read the complete articleFixed-tour sortie set-packing B&B
Represent candidate conflicts as binary set-packing inequalities.
Complexity. Exponential worst case
Read the complete articleQUBO + classical annealing
Reward savings and penalize simultaneous conflicting sorties.
Complexity. Restarts × sweeps × candidate interactions
Read the complete articleBest-improvement VND
Search several neighborhoods and accept the best exactly reevaluated move.
Complexity. Neighborhood- and round-dependent
Read the complete articleRoute-first, split-second
Decompose route construction from synchronization-aware sortie selection.
Complexity. Depends on route and split modes
Read the complete articleDeterministic Hadoop/Spark experiment planner
Stable case IDs and content hashes keep distribution separate from solver semantics.
Complexity. O(c log c) orchestration around solver cost
Read the complete article