Graph Shortest-Path Calculator (Dijkstra) implementation

Binding contract

This record describes what an executable surface must bind and validate. It does not claim that a public calculator, package, or production route is deployed.

Record owner

Guth Instruments

Lifecycle

verified-clean

Evidence ID

t6-092

Effect

Computation or source lookup only

Input and validation requirements

A negative edge weight is a hard domain break for standard Dijkstra. The calculator must reject it; accepting it and returning a computed path would make the result potentially incorrect. Edge-direction conventions can also change a valid result from distance 1 to unreachable.

Required corrections

No binding erratum is attached to this unique-name record. Implementers must still preserve the declared units, domain, and failure behavior.

Inspectable interface fixture

The sample below is evidence for interface and validation tests, not a production implementation.

{
  "inputs": {
    "nodes": [
      "A",
      "B",
      "C",
      "D",
      "E"
    ],
    "directed": false,
    "edges": [
      [
        "A",
        "B",
        4
      ],
      [
        "A",
        "C",
        1
      ],
      [
        "C",
        "B",
        2
      ],
      [
        "B",
        "D",
        1
      ],
      [
        "C",
        "D",
        5
      ],
      [
        "D",
        "E",
        3
      ],
      [
        "B",
        "E",
        10
      ]
    ],
    "source": "A",
    "target": "E",
    "trace_rule": "record each vertex when finalized; stop after target finalization"
  },
  "expected_outputs": {
    "shortest_path": [
      "A",
      "C",
      "B",
      "D",
      "E"
    ],
    "total_distance": 7,
    "visited_order": [
      "A",
      "C",
      "B",
      "D",
      "E"
    ]
  },
  "working": "Initialize: d(A)=0; d(B)=d(C)=d(D)=d(E)=infinity. Extract A(0): d(B)=min(infinity,0+4)=4; d(C)=min(infinity,0+1)=1. Extract C(1): d(B)=min(4,1+2)=3; d(D)=min(infinity,1+5)=6. Extract B(3): d(D)=min(6,3+1)=4; d(E)=min(infinity,3+10)=13. Extract D(4): d(E)=min(13,4+3)=7. Extract E(7): target finalized. Final path is A-C-B-D-E and distance 7."
}

Other records

Sources and evidence

These pointers bind the page to evidence. They do not grant authority or collapse verification into deployment.

• VERIFIED_LEDGER.json
• evidence-tranche6/tranche6-results.json