Shortest path potential check
shortest-path-potential-check · version 1.0.0 · Numbers & math · free, no key needed
Check claimed single-source shortest-path distances against a weighted digraph: edge inequalities and attainment.
Use when you need to: verify single source shortest path distances · check claimed distance table · bellman optimality check for distances.
Decide before calling
Read the versioned contract and the supported scope below. Reuse shortest-path-potential-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-potential-check@1.0.0 for verify single source shortest path distances. 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 single source shortest path distances
- check claimed distance table
- bellman optimality check for distances
- validate dijkstra output
- check bellman ford result
- shortest path distance certificate
- triangle inequality check on graph distances
Not supported
- computing distances (the caller supplies the claim)
- all-pairs distance matrices
- graphs with a reachable negative-weight cycle (every claim is rejected at the first violated edge)
- floating-point weights
Behavior
- Check order: source listed; distances entries in array order (unknown_vertex, duplicate_vertex at the second occurrence); coverage of graph.vertices in order (missing_vertex); source distance exactly 0 (source_distance_not_zero); every edge in graph.edges order with a finite tail d(u) needs a finite head (unreachable_mark_contradicted) and d(v) <= d(u) + w (edge_not_relaxed); finally every finite vertex in graph.vertices order must be reached from the source through tight edges d(u) + w = d(v) (distance_not_attained).
- Passing every stage proves d = delta(s, .) exactly: the inequalities give d <= delta and tight-edge attainment gives d >= delta (zero-weight cycles cannot fake attainment). A reachable negative cycle makes every claim fail.
- Distances are canonical integer strings of at most 40 digits, or null for +infinity (unreachable); edges with a null tail impose no constraint. Arithmetic is exact (big integers).
- For edge failures first_discrepancy.expected is the bound d(u) + w and actual is the claimed d(v) (null when marked unreachable); index is the position in the field named by first_discrepancy.field.
- Vertex 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 64distances(array of object, required): max items 500
Output
valid(boolean, required)reason(one of null, "unknown_vertex", "duplicate_vertex", "missing_vertex", "source_distance_not_zero", "unreachable_mark_contradicted", "edge_not_relaxed", "distance_not_attained", required)first_discrepancy(object or null, required)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 distance entries: 500
Example
Request 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",
"distances": [
{
"vertex": "s",
"distance": "0"
},
{
"vertex": "t",
"distance": "8"
},
{
"vertex": "x",
"distance": "9"
},
{
"vertex": "y",
"distance": "5"
},
{
"vertex": "z",
"distance": "7"
}
]
}Response:
{
"result": {
"valid": true,
"reason": null,
"first_discrepancy": null,
"reference_version": "clrs-4e-2022-ch22-single-source-shortest-paths"
}
}How to call it
MCP
Connect https://computefirst.net/mcp (setup), then call execute with:
{
"id": "shortest-path-potential-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",
"distances": [
{
"vertex": "s",
"distance": "0"
},
{
"vertex": "t",
"distance": "8"
},
{
"vertex": "x",
"distance": "9"
},
{
"vertex": "y",
"distance": "5"
},
{
"vertex": "z",
"distance": "7"
}
]
}
}HTTP (no key)
curl -X POST https://computefirst.net/v1/tools/shortest-path-potential-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","distances":[{"vertex":"s","distance":"0"},{"vertex":"t","distance":"8"},{"vertex":"x","distance":"9"},{"vertex":"y","distance":"5"},{"vertex":"z","distance":"7"}]}'The machine-readable contract is at /v1/tools/shortest-path-potential-check/versions/1.0.0.
CLI
node cli.mjs run shortest-path-potential-check 1.0.0 --input input.json --base-url https://computefirst.netGet the client at /clients/cli/.
Related tools
- Shortest path certificate check: Check a claimed shortest s-t path and distance in a weighted digraph using a caller-supplied potential certificate.
- Filter result check: Checks an exact claimed decimal filter result with source-order witnesses.
- Graph path weight check: Check that a path of edge IDs walks source to target in a weighted digraph and sums to the claimed exact weight.
- Join inner result check: Check a claimed ordered inner join index result and report its first discrepancy.
- Join left result check: Check a claimed ordered left join index result and report its first discrepancy.
- Join semi result check: Check a claimed ordered semi-join index result and report its first discrepancy.