The Davis Manifold Framework for Single-Source Shortest Paths: Curvature-Aware Graph Algorithms

We present the Davis Manifold Framework, a novel approach to single-source shortest path (SSSP) computation that reinterprets graph structure through discrete differential geometry. By classifying vertices according to local curvature—measured via degree distribution—we develop algorithms that exploit geometric regularity in "flat" regions while adapting to high-curvature hubs. Core Mathematical Insight The framework derives from the Davis Law of the Field Equations of Semantic Coherence: C = τ / K where: C = inference capacity (ability to complete unobserved states) τ = tolerance budget K = curvature This fundamental relationship states that low-curvature regions admit aggressive path propagation, while high-curvature regions require careful exploration. Discrete Curvature Definition For a vertex v, we define the connectivity curvature proxy: κ(v) = (deg(v) − d̄) / d̄ where deg(v) is out-degree and d̄ is average degree. κ < 0 → "flat" vertex (below-average connectivity) κ > 0 → "curved" hub (above-average connectivity) Algorithm Variants Davis-Δ — Curvature-aware delta-stepping with light/heavy edge classification Davis-Corridor — Geodesic corridor scouting in flat regions (deg ≤ 4) Davis-Deep — Multi-hop propagation (2-3 hops) with adaptive thresholds Davis-Hub — Batch relaxation for high-curvature vertices (deg ≥ 2d̄) Key Results 80% win rate against optimized Dijkstra (20/25 test configurations) Up to 2.14× speedup on sparse graphs (n=5000, avg degree 4) Correctness verified against baseline within tolerance 10⁻⁹ Graph Type Davis Wins Avg Speedup Sparse 5/5 1.75× Clustered 5/5 1.23× Grid 3/5 1.24× Road-like 2/5 1.19× Dense 5/5 1.03× Theoretical Foundation The Corridor Propagation Safety Lemma guarantees correctness: updating tentative distances without marking vertices finalized preserves Dijkstra's invariant. The heap ensures eventual correct processing. The Geometric Trichotomy parameter: Γ = (m · τ) / (K̂_max · log|S|) When Γ > 1 (determined regime), shortest paths are unique and stable—precisely where corridor scouting succeeds. Contents davis_manifold_sssp.tex — Full LaTeX paper davis_manifold_sssp.pdf — Compiled paper (10 pages) sssp_rust/ — Complete Rust implementation with benchmarks visualizations/ — Benchmark plots and algorithm animations Citation This work extends the Field Equations of Semantic Coherence (Davis, 2025): https://doi.org/10.5281/zenodo.17771796 Keywords shortest path, Dijkstra, graph algorithms, discrete geometry, curvature, manifold, delta-stepping, SSSP, Rust, benchmarking PATENT PENDING U.S. Provisional Application No. 63/962,503 (filed Jan. 17, 2026)"Curvature-Aware Adaptive Algorithm Selection for Single-Source Shortest Path Computation" Commercial use may require license. Academic use permitted with citation.