# Baseline Benchmarks — Floyd-Warshall

Date: 2026-06-09  
Commit: 5f5b97a  
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

## size_scaling — sparse graph, 1 provider

| Nodes | Time (median) | Ratio vs prev | Expected V³ ratio |
|------:|--------------|:-------------:|:-----------------:|
|    10 |     134 µs   |      —        |        —          |
|    20 |    1.17 ms   |     8.7x      |       8.0x        |
|    30 |    3.76 ms   |     3.2x      |       3.4x        |
|    40 |    8.99 ms   |     2.4x      |       2.4x        |
|    50 |   18.11 ms   |     2.0x      |       2.0x        |

Scaling closely follows O(V³) theory at all sizes.

## provider_scaling — sparse graph, 30 nodes

| Providers | Time (median) |
|----------:|--------------|
|         1 |    3.84 ms   |
|         3 |    3.91 ms   |
|         5 |    3.87 ms   |

Provider count has negligible impact — the `unique_cheapest_edges` deduplication pass
is dominated by the O(V³) triple loop.

## edge_density — 1 provider, 30 nodes

| Topology        | Edges | Time (median) | Overhead |
|:----------------|------:|--------------|:--------:|
| Sparse (ring)   |    30 |    3.84 ms   |    —     |
| Dense (all-pairs)| 870  |    4.68 ms   |  +22%    |

Dense graphs add ~22% overhead at 30 nodes, attributable to matrix initialisation
and `unique_cheapest_edges`; the triple loop itself is unaffected by edge count.
