# Optimized Benchmarks — Floyd-Warshall

Date: 2026-06-09  
Criterion sample size: 10  
Graph topology: ring (sparse), all-pairs (dense)  
Edge rates: all < 1.0 (range 0.5–0.6), scaled by 10^12

## Optimizations applied

1. **Flat Vec cost/next-hop matrices** (was `BTreeMap<Pair, Path>`): O(1) indexed, contiguous memory.
2. **Next-hop table replaces Vec::clone in O(n³) loop**: paths reconstructed once after the loop — O(n⁴) → O(n²) allocation work.
3. **Plain `0..n` range loops** (was `BTreeSet` iteration): compiler-friendly, eliminates tree pointer-chasing.
4. **Early termination** when `cost[i*n+k]` is infinite: skips unreachable rows in the inner loop.
5. **Single deduplication pass** in `longest_paths_mult` (was calling `unique_cheapest_edges` twice).

## size_scaling — sparse graph, 1 provider

| Nodes | Before    | After    | Speedup |
|------:|-----------|----------|:-------:|
|    10 |  134 µs   |  71 µs   |  1.9×   |
|    20 | 1.17 ms   | 529 µs   |  2.2×   |
|    30 | 3.76 ms   | 1.73 ms  |  2.2×   |
|    40 | 8.99 ms   | 4.27 ms  |  2.1×   |
|    50 | 18.11 ms  | 7.84 ms  |  2.3×   |

## provider_scaling — sparse graph, 30 nodes

| Providers | Before   | After    | Speedup |
|----------:|----------|----------|:-------:|
|         1 | 3.84 ms  | 1.75 ms  |  2.2×   |
|         3 | 3.91 ms  | 1.71 ms  |  2.3×   |
|         5 | 3.87 ms  | 1.73 ms  |  2.2×   |

## edge_density — 1 provider, 30 nodes

| Topology         | Edges | Before   | After    | Speedup |
|:-----------------|------:|----------|----------|:-------:|
| Sparse (ring)    |    30 | 3.84 ms  | 1.68 ms  |  2.3×   |
| Dense (all-pairs)| 870   | 4.68 ms  | 616 µs   |  7.6×   |

The dense graph benefits disproportionately: dense paths are longer, so each `Vec::clone`
in the old O(n³) loop was copying more edges per iteration. The flat next-hop table
reduces that to a single `usize` copy regardless of path length.
