Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

BFS: shortest paths and an explicit linear event bound

Proved
CLRS.BFS.correctness_and_explicit_running_time

by Chutong · Oct 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

algo2leanalgorithmsclrsgraph-theoryrunning-timetextbook

For every heap representing the input graph and every valid source, establish one terminating BFS Call with the complete shortest-path, predecessor, fresh-result, and caller-preservation postcondition. For the same call, prove

T≤6n+2m+5.T\le 6n+2m+5.T≤6n+2m+5.

Here T is the increment of graph_work and m counts adjacency occurrences. The initial clock values are arbitrary. This stronger numerical bound is an open supporting task.

Preamble
import Definitions.Def_CLRS_BFS_Program

set_option autoImplicit false

open Algo2LeanGenerated CLRS.GraphTraversal CLRS.BFS
Formal statement
theorem CLRS.BFS.correctness_and_explicit_running_time
    (before : Heap) (graph : ObjectRef) (g : Graph) (source : Int)
    (represented : GraphRep before graph g) (sourceValid : Vertex g source) :
    ∃ after result,
      Algo.bfs.bfs.Call before (graph, source) after result ∧
      Post before after result g source ∧
      work before after ≤ 6 * g.size + 2 * edgeCount g + 5 := by
  sorry
Source
CLRS, Introduction to Algorithms, fourth edition (MIT Press, 2022), Chapter 20, §20.2. https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/ ; new arrays-of-arrays implementation compiled with Algo2Lean v0.1.4, https://www.algo2lean.com/versions/v0.1.4/ . Source filenames and full code are in the mission description.
Read-back

What the Lean code literally says, in plain math · GPT-6 (Codex, independent fresh-context agent)

For every initial heap, natural-number object reference, mathematical graph consisting of a natural number VVV and a finite neighbor list for each natural-number index whose entries are all below VVV whenever its index is below VVV, and integer source sss, assume the heap represents that graph at the given object reference and 0≤s<V0≤s<V0≤s<V. Representation means that the reference names an allocated graph_input.UnweightedGraph object with size field VVV and fields naming an allocated Seq[Int] adjacency collection and an allocated integer degree sequence; for each u<Vu<Vu<V, the degree entry is the neighbor-list length, the adjacency entry decodes to an allocated row sequence, and that row's prefix of this length equals the neighbor list in order. The conclusion asserts existence of a final heap and a result-object reference such that the generated BFS function, from this input heap, graph reference, and source, has a finite execution returning that same final heap and result under every suspended caller stack, including completion at the top level. That very final heap contains an allocated bfs.BFSResult object whose reference is at least the initial object-allocation counter and strictly below the final one. Its distance and parent fields name distinct integer sequences whose references are each at least the initial sequence counter and strictly below the final one. Writing d(v)d(v)d(v) and p(v)p(v)p(v) for their final values, the source has d(s)=0d(s)=0d(s)=0 and p(s)=−1p(s)=-1p(s)=−1, and every vertex integer vvv in 0≤v<V0≤v<V0≤v<V has d(v)≥−1d(v)≥-1d(v)≥−1. Its distance is −1-1−1 exactly when there is no directed walk from sss to vvv; if its distance is nonnegative, a walk of that natural-number length exists and no shorter walk exists. Walks use neighbor-list membership as directed edges, may repeat vertices, and allow a zero-length walk at any valid vertex. A vertex of distance −1-1−1 also has parent −1-1−1. Every nonsource vertex of nonnegative distance has a valid parent vertex with an edge to it and satisfies d(p(v))+1=d(v)d(p(v))+1=d(v)d(p(v))+1=d(v). The final heap preserves the entire contents of every initially allocated integer sequence, object, and collection; none of the three allocation counters decreases, the graph_work clock does not decrease, and every other named clock stays unchanged. The difference between the final and initial graph_work clocks is at most 6V+2E+56V+2E+56V+2E+5, where EEE is the sum of the neighbor-list lengths over u<Vu<Vu<V, counting repeated adjacency occurrences. The bound is on the explicit instrumented ticks of this same execution, measured from arbitrary initial clock values; it does not count a prior construction of the supplied graph or separately charge every transition or integer operation. The premises permit self-loops, parallel arcs, and compatible sharing of adjacency-row storage; they do not constrain unused row entries, graph-list indices outside the vertex range, or unrelated heap contents. The valid-source premise makes the implication vacuous for V=0V=0V=0. The output specification imposes no requirements on output entries outside the vertex range and no exact count of additional allocated objects or sequences. This is an unproved goal: its body is sorry, so the displayed declaration supplies no proof of the asserted existence, correctness, preservation, freshness, or bound.

Human review
  • Endorsed by Shuze Chen · Oct 15, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Chutong · Oct 15, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me