import { SSSPGraph, SSSPResult, PivotSet } from '../types.js';
/**
 * SSSP Router implementing the Breaking the Sorting Barrier algorithm.
 *
 * Key insight: For multi-source shortest paths, use pivot-based recursion
 * to achieve O(m log^(2/3) n) instead of Dijkstra's O(m + n log n).
 *
 * Parameters:
 *   k = floor(cbrt(log(n))) — pivot threshold
 *   t = floor(log(n)^(2/3)) — recursion depth bound
 *
 * FindPivots: Run k rounds of Bellman-Ford relaxation, collect vertices
 *   reachable within k hops. Sources with SP tree >= k vertices → pivots.
 *   Key property: |P| <= |U|/k, geometric problem reduction.
 *
 * BMSSP: Recursive divide-and-conquer. Base case: |S|=1 or t=0 → Dijkstra.
 *   Find pivots → recurse on pivots → inherit distances for remaining.
 */
export declare class SSSPRouter {
    private graph;
    private cache;
    /** Build adjacency graph from mesh node connections */
    buildGraph(nodes: Array<{
        id: string;
        connections: Array<{
            targetId: string;
            latency: number;
        }>;
    }>): SSSPGraph;
    /** Add a single edge to the graph */
    addEdge(from: string, to: string, weight: number): void;
    /**
     * FindPivots(G, S, k):
     * 1. Initialize distances for all v ∈ S to 0
     * 2. Run k rounds of Bellman-Ford relaxation (not full BF, just k steps)
     * 3. Collect U = vertices reachable within k hops
     * 4. For each source s: if SP tree covers >= k vertices → mark as pivot
     * 5. Return pivot set P and uncovered vertices
     */
    findPivots(graph: SSSPGraph, sources: string[], k: number): PivotSet;
    /**
     * BMSSP(G, S, t) — Bounded Multi-Source Shortest Path:
     * 1. If |S| = 1 or t = 0: base case → simple Dijkstra
     * 2. FindPivots(G, S, k) to identify pivot sources
     * 3. Recursively solve SSSP(G, P) with t-1
     * 4. For remaining vertices: inherit distance bounds from nearest pivot
     */
    bmssp(graph: SSSPGraph, sources: string[], t: number): SSSPResult;
    /** Standard Dijkstra with min-heap for single-source shortest path */
    dijkstra(graph: SSSPGraph, source: string): SSSPResult;
    /** Find optimal route between two nodes */
    route(fromNode: string, toNode: string): string[];
    /** Reconstruct path from predecessor map */
    private reconstructPath;
    /** Clear route cache */
    clearCache(): void;
}
//# sourceMappingURL=sssp-router.d.ts.map