Graph Shortest-Path Calculator (Dijkstra) mechanism

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

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