ALGORITHM ARTICLE
Dijkstra shortest path
Problem. Minimum-weight source-to-target path with nonnegative edge weights.
Core idea. Permanently settle the smallest tentative distance; nonnegative weights ensure that label can never improve later.
Procedure
- Set the source label to zero.
- Extract the smallest unsettled label from a heap.
- Relax outgoing edges and recover the predecessor chain.
Certificate. Registered-edge path plus label-setting optimality.
Data structures and API
from optfin_orlab import ExactGraphOracle
solver = ExactGraphOracle()
result = solver.shortest_path(...)Complexity. O((|V|+|E|) log |V|)
Limits. Negative edge weights require another method.
OPTFIN AUDIT CHECKS
What has to reconcile before this method is trusted.
- DefinitionProblem, objective, inputs and output are explicit.
- Data structureThe public API and canonical source path are identified.
- CorrectnessRegistered-edge path plus label-setting optimality.
- ComplexityO((|V|+|E|) log |V|)
- Operational limitNegative edge weights require another method.
- ReproductionSource, executable test and evidence route remain linked.
LUNA ACADEMIC
Continue this algorithm in one research conversation.
Ask for the paper trail, executable test, source explanation, or a reproducibility plan for Dijkstra shortest path.
Open Luna for this algorithm