Source: https://guthlabs.ai/docs/instruments/graph-shortest-path-calculator-dijkstra/mechanism/

instrument mechanism / verified-clean

# Graph Shortest-Path Calculator (Dijkstra) mechanism

The inspectable method record for Graph Shortest-Path Calculator (Dijkstra), kept separate from implementation and qualification.

Status: **VERIFIED_CLEAN**Lifecycle: **verified-clean**

## Model scope

The core algorithm claim is standard and correct under the non-negative-weight constraint. Verdict is NEEDS_REVIEW because graph direction, trace semantics, tie-breaking, and unreachable-target representation are unspecified. The four vectors use exact arithmetic and unique priority values except for the explicitly tested zero-distance edge and source-equals-target boundary case.

- Dijkstra's algorithm with a min-priority queue is the standard correct method for shortest paths with non-negative edge weights.

- The specification does not define whether the edge list represents a directed or undirected graph.

- The visited-order trace is ambiguous: it must specify whether vertices are recorded when extracted/finalized, whether the source is included, whether processing stops when the target is finalized, and how equal-priority ties are broken.

- The specification does not define the output for an unreachable target, such as an empty path and an infinite distance.

- The implementation should reject or clearly report negative, NaN, or otherwise invalid edge weights rather than silently applying Dijkstra.

## Units and conventions

- Edge weights are additive costs in one common unit, or are dimensionless; weights from incompatible units must not be mixed.

- Zero-weight edges are allowed.

- All edge weights must be finite and non-negative; negative weights require another algorithm such as Bellman-Ford.

- Distances should use a representation that avoids unsafe integer overflow or unacceptable floating-point accumulation error.

- These vectors assume vertices are finalized in min-distance order, the source is included in the trace, processing stops when the target is finalized, and no equal-priority tie occurs unless explicitly stated.

## Inspectable vector

One of 4 source-bound review vectors:

````
{
  "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."
}
````

## Failure boundary

**BREAK_CLAIMED** · SELF_FLAGGED

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.

## Other records

[01**Overview**](<https://guthlabs.ai/docs/instruments/graph-shortest-path-calculator-dijkstra/>)[03**Implementation**](<https://guthlabs.ai/docs/instruments/graph-shortest-path-calculator-dijkstra/implementation/>)[04**Qualification**](<https://guthlabs.ai/docs/instruments/graph-shortest-path-calculator-dijkstra/qualification/>)

## 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`

- `BOUNDARY_HAZARD_CATALOG.json`