An algorithm can do more work for two different reasons: there is more input to inspect, or it keeps inspecting the same input. My SPFA study separates those two effects.
Count the work, not just the seconds.
The study examines the plain FIFO version of the Shortest Path Faster Algorithm on positive-weight directed graphs. Increasing density adds edges that must be scanned. Queue ordering can also cause vertices to be processed again, repeating those scans.
I investigated edge-scan counts, repeated scanning and queue removals alongside measured runtime. The distinction matters: a slower run alone does not explain which mechanism produced the extra work.
What this can—and cannot—say.
Work counters help distinguish the cost of a larger graph from the cost of revisiting it. They do not make every share of scan growth a causal share of wall-clock runtime. Timing still depends on the implementation and test conditions.
The study grew out of my algorithm training and includes a later additional graph cohort. The later code audit, timing collection, statistical corrections and English revision were AI-assisted; I do not present that phase as independently executed work.
Return to selected work