# Shortest path certificate check

`shortest-path-certificate-check` · version 1.0.0 · Numbers & math · free, no key needed

Check a claimed shortest s-t path and distance in a weighted digraph using a caller-supplied potential certificate.

**Use when you need to: verify shortest path certificate · prove path is shortest with potentials · check claimed shortest path and distance.**

## Decide before calling

Read the [versioned contract](/v1/tools/shortest-path-certificate-check/versions/1.0.0) and the supported scope below. Reuse `shortest-path-certificate-check@1.0.0` when your input, required output and limits match it. Choose another approach for an unsupported operation.

## Explain the choice

"I can use `shortest-path-certificate-check@1.0.0` for verify shortest path certificate. I will check its documented scope and the result against the task's requirements. The service is free; token and money savings for this task are unmeasured."

## Supported

- verify shortest path certificate
- prove path is shortest with potentials
- check claimed shortest path and distance
- check optimality of weighted route
- certify no path between two vertices
- feasible potential certificate check
- shortest st path optimality proof

## Not supported

- searching for a shortest path or building the certificate
- certificates other than vertex potentials (for example predecessor trees alone)
- negative-cycle detection reports (a reachable negative cycle simply makes every certificate fail)
- floating-point weights

## Behavior

- Check order: source then target listed; if path_edge_ids is not null, walk it (missing_edge, path_discontinuity, path_target_mismatch) and compare its exact weight with claimed_distance (claimed_distance_mismatch); potentials in array order (unknown_vertex, duplicate_vertex) and coverage of graph.vertices (missing_vertex); source potential exactly 0 (source_potential_not_zero); every edge in graph.edges order with a finite tail p(u) needs a finite head (unreachable_mark_contradicted) and p(v) <= p(u) + w (edge_not_relaxed); finally p(target) must equal claimed_distance (target_potential_mismatch).
- path_edge_ids and claimed_distance are both null (claim: no path from source to target) or both non-null; a mismatch throws invalid_input.
- Soundness: telescoping p(v) - p(u) <= w along any source-target walk gives weight >= p(target) - p(source) = claimed_distance, and the path attains it, so a valid result proves optimality; with p(target) = null, feasibility proves the target unreachable. Potentials need not equal the true distances elsewhere.
- Integers are canonical strings of at most 40 digits (null = +infinity) and arithmetic is exact; path_weight is the walked weight when the walk is structurally valid, otherwise null.
- IDs are compared code unit for code unit; graph errors throw invalid_input and size limits throw limit_exceeded before per-item work.
- Reference: CLRS 4th ed. (2022) chapter 22, sections 22.4-22.5; reference_version "clrs-4e-2022-ch22-single-source-shortest-paths".

## Input

- `graph` (object, required)
- `source` (string, required): min length 1; max length 64
- `target` (string, required): min length 1; max length 64
- `path_edge_ids` (array or null, required): max items 2000
- `claimed_distance` (string or null, required): pattern `^(0|-?[1-9][0-9]*)$`
- `potentials` (array of object, required): max items 500

## Output

- `valid` (boolean, required)
- `reason` (one of null, "unknown_vertex", "missing_edge", "path_discontinuity", "path_target_mismatch", "claimed_distance_mismatch", "duplicate_vertex", "missing_vertex", "source_potential_not_zero", "unreachable_mark_contradicted", "edge_not_relaxed", "target_potential_mismatch", required)
- `first_discrepancy` (object or null, required)
- `path_weight` (string or null, required): pattern `^(0|-?[1-9][0-9]*)$`
- `reference_version` (constant "clrs-4e-2022-ch22-single-source-shortest-paths", required)

## Limits

- max vertices: 500
- max edges: 2000
- max id bytes: 64
- max integer digits: 40
- max path edges: 2000
- max potential entries: 500

## Example

Request input:

```json
{
  "graph": {
    "vertices": [
      "s",
      "t",
      "x",
      "y",
      "z"
    ],
    "edges": [
      {
        "id": "st",
        "from": "s",
        "to": "t",
        "weight": "10"
      },
      {
        "id": "sy",
        "from": "s",
        "to": "y",
        "weight": "5"
      },
      {
        "id": "tx",
        "from": "t",
        "to": "x",
        "weight": "1"
      },
      {
        "id": "ty",
        "from": "t",
        "to": "y",
        "weight": "2"
      },
      {
        "id": "yt",
        "from": "y",
        "to": "t",
        "weight": "3"
      },
      {
        "id": "yx",
        "from": "y",
        "to": "x",
        "weight": "9"
      },
      {
        "id": "yz",
        "from": "y",
        "to": "z",
        "weight": "2"
      },
      {
        "id": "xz",
        "from": "x",
        "to": "z",
        "weight": "4"
      },
      {
        "id": "zs",
        "from": "z",
        "to": "s",
        "weight": "7"
      },
      {
        "id": "zx",
        "from": "z",
        "to": "x",
        "weight": "6"
      }
    ]
  },
  "source": "s",
  "target": "x",
  "path_edge_ids": [
    "sy",
    "yt",
    "tx"
  ],
  "claimed_distance": "9",
  "potentials": [
    {
      "vertex": "s",
      "potential": "0"
    },
    {
      "vertex": "t",
      "potential": "8"
    },
    {
      "vertex": "x",
      "potential": "9"
    },
    {
      "vertex": "y",
      "potential": "5"
    },
    {
      "vertex": "z",
      "potential": "7"
    }
  ]
}
```

Response:

```json
{
  "result": {
    "valid": true,
    "reason": null,
    "first_discrepancy": null,
    "path_weight": "9",
    "reference_version": "clrs-4e-2022-ch22-single-source-shortest-paths"
  }
}
```

## How to call it

### MCP

Connect `https://computefirst.net/mcp` ([setup](/docs#connect)), then call `execute` with:

```json
{
  "id": "shortest-path-certificate-check",
  "version": "1.0.0",
  "input": {
    "graph": {
      "vertices": [
        "s",
        "t",
        "x",
        "y",
        "z"
      ],
      "edges": [
        {
          "id": "st",
          "from": "s",
          "to": "t",
          "weight": "10"
        },
        {
          "id": "sy",
          "from": "s",
          "to": "y",
          "weight": "5"
        },
        {
          "id": "tx",
          "from": "t",
          "to": "x",
          "weight": "1"
        },
        {
          "id": "ty",
          "from": "t",
          "to": "y",
          "weight": "2"
        },
        {
          "id": "yt",
          "from": "y",
          "to": "t",
          "weight": "3"
        },
        {
          "id": "yx",
          "from": "y",
          "to": "x",
          "weight": "9"
        },
        {
          "id": "yz",
          "from": "y",
          "to": "z",
          "weight": "2"
        },
        {
          "id": "xz",
          "from": "x",
          "to": "z",
          "weight": "4"
        },
        {
          "id": "zs",
          "from": "z",
          "to": "s",
          "weight": "7"
        },
        {
          "id": "zx",
          "from": "z",
          "to": "x",
          "weight": "6"
        }
      ]
    },
    "source": "s",
    "target": "x",
    "path_edge_ids": [
      "sy",
      "yt",
      "tx"
    ],
    "claimed_distance": "9",
    "potentials": [
      {
        "vertex": "s",
        "potential": "0"
      },
      {
        "vertex": "t",
        "potential": "8"
      },
      {
        "vertex": "x",
        "potential": "9"
      },
      {
        "vertex": "y",
        "potential": "5"
      },
      {
        "vertex": "z",
        "potential": "7"
      }
    ]
  }
}
```

### HTTP (no key)

```sh
curl -X POST https://computefirst.net/v1/tools/shortest-path-certificate-check/versions/1.0.0/execute \
  -H "Content-Type: application/json" \
  -d '{"graph":{"vertices":["s","t","x","y","z"],"edges":[{"id":"st","from":"s","to":"t","weight":"10"},{"id":"sy","from":"s","to":"y","weight":"5"},{"id":"tx","from":"t","to":"x","weight":"1"},{"id":"ty","from":"t","to":"y","weight":"2"},{"id":"yt","from":"y","to":"t","weight":"3"},{"id":"yx","from":"y","to":"x","weight":"9"},{"id":"yz","from":"y","to":"z","weight":"2"},{"id":"xz","from":"x","to":"z","weight":"4"},{"id":"zs","from":"z","to":"s","weight":"7"},{"id":"zx","from":"z","to":"x","weight":"6"}]},"source":"s","target":"x","path_edge_ids":["sy","yt","tx"],"claimed_distance":"9","potentials":[{"vertex":"s","potential":"0"},{"vertex":"t","potential":"8"},{"vertex":"x","potential":"9"},{"vertex":"y","potential":"5"},{"vertex":"z","potential":"7"}]}'
```

The machine-readable contract is at [/v1/tools/shortest-path-certificate-check/versions/1.0.0](/v1/tools/shortest-path-certificate-check/versions/1.0.0).

### CLI

```sh
node cli.mjs run shortest-path-certificate-check 1.0.0 --input input.json --base-url https://computefirst.net
```

Get the client at [/clients/cli/](/clients/cli/).

## Related tools

- [Lp dual feasibility check](/tools/lp-dual-feasibility-check): Check that LP dual multipliers satisfy y >= 0 and yA >= c exactly; return the proven upper bound y.b.
- [Lp optimality certificate check](/tools/lp-optimality-certificate-check): Check an LP optimum claim from a primal x and dual y: feasibility, complementary slackness and zero duality gap.
- [Maximum flow certificate check](/tools/maximum-flow-certificate-check): Check a claimed max flow with a min-cut certificate or residual search; reports the first failure or augmenting path.
- [Shortest path potential check](/tools/shortest-path-potential-check): Check claimed single-source shortest-path distances against a weighted digraph: edge inequalities and attainment.
- [Chromatic certificate check](/tools/chromatic-certificate-check): Check a claim chi(G) = k: a proper k-colouring plus a clique or bounded exhaustive proof; returns the first discrepancy.
- [Interval duration check](/tools/interval-duration-check): Check a claimed duration between two RFC 3339 instants as exact elapsed time or as a calendar duration.