Module certificate 

Verifiable certificates for MST and shortest-path results.

Every certificate-producing algorithm ships a verifier that re-checks the result from scratch and never trusts the producer. verify_mst checks edge count, acyclicity, spanning connectivity, the recorded total weight, and optimality (the cycle property). verify_shortest_paths checks predecessor consistency and edge relaxation.

Structs

MstCertificate

A compact, checkable MST witness.

ShortestPathCertificate

A shortest-path tree witness from a single source.

SpanningTree

A spanning tree result: tree edge ids (ascending) and the total weight.

Functions

verify_mst

Verify that cert describes a minimum spanning tree of graph.

verify_shortest_paths

Verify that cert is a valid shortest-path tree of graph from its source.