{"id":"shortest-path-certificate-check","version":"1.0.0","description":"Check a claimed shortest s-t path and distance in a weighted digraph using a caller-supplied potential certificate.","supported_operations":["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"],"unsupported_operations":["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"],"semantics":["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\"."],"limits":{"max_vertices":500,"max_edges":2000,"max_id_bytes":64,"max_integer_digits":40,"max_path_edges":2000,"max_potential_entries":500},"pricing":{"status":"unpriced","charge_usd":null},"input_schema":{"type":"object","additionalProperties":false,"required":["graph","source","target","path_edge_ids","claimed_distance","potentials"],"properties":{"graph":{"type":"object","additionalProperties":false,"required":["vertices","edges"],"properties":{"vertices":{"type":"array","minItems":1,"maxItems":500,"items":{"type":"string","minLength":1,"maxLength":64}},"edges":{"type":"array","maxItems":2000,"items":{"type":"object","additionalProperties":false,"required":["id","from","to","weight"],"properties":{"id":{"type":"string","minLength":1,"maxLength":64},"from":{"type":"string","minLength":1,"maxLength":64},"to":{"type":"string","minLength":1,"maxLength":64},"weight":{"type":"string","pattern":"^(0|-?[1-9][0-9]*)$"}}}}}},"source":{"type":"string","minLength":1,"maxLength":64},"target":{"type":"string","minLength":1,"maxLength":64},"path_edge_ids":{"type":["array","null"],"maxItems":2000,"items":{"type":"string","minLength":1,"maxLength":64}},"claimed_distance":{"type":["string","null"],"pattern":"^(0|-?[1-9][0-9]*)$"},"potentials":{"type":"array","maxItems":500,"items":{"type":"object","additionalProperties":false,"required":["vertex","potential"],"properties":{"vertex":{"type":"string","minLength":1,"maxLength":64},"potential":{"type":["string","null"],"pattern":"^(0|-?[1-9][0-9]*)$"}}}}}},"output_schema":{"type":"object","additionalProperties":false,"required":["valid","reason","first_discrepancy","path_weight","reference_version"],"properties":{"valid":{"type":"boolean"},"reason":{"type":["string","null"],"enum":[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"]},"first_discrepancy":{"type":["object","null"],"additionalProperties":false,"required":["field","index","vertex","edge_id","expected","actual"],"properties":{"field":{"type":"string","enum":["source","target","path_edge_ids","claimed_distance","potentials","graph.vertices","graph.edges"]},"index":{"type":["integer","null"],"minimum":0},"vertex":{"type":["string","null"]},"edge_id":{"type":["string","null"]},"expected":{"type":["string","null"]},"actual":{"type":["string","null"]}}},"path_weight":{"type":["string","null"],"pattern":"^(0|-?[1-9][0-9]*)$"},"reference_version":{"type":"string","const":"clrs-4e-2022-ch22-single-source-shortest-paths"}}},"examples":[{"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"}]},"output":{"valid":true,"reason":null,"first_discrepancy":null,"path_weight":"9","reference_version":"clrs-4e-2022-ch22-single-source-shortest-paths"}},{"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","yz","zx"],"claimed_distance":"13","potentials":[{"vertex":"s","potential":"0"},{"vertex":"t","potential":"8"},{"vertex":"x","potential":"9"},{"vertex":"y","potential":"5"},{"vertex":"z","potential":"7"}]},"output":{"valid":false,"reason":"target_potential_mismatch","first_discrepancy":{"field":"potentials","index":2,"vertex":"x","edge_id":null,"expected":"13","actual":"9"},"path_weight":"13","reference_version":"clrs-4e-2022-ch22-single-source-shortest-paths"}}],"execute_url":"/v1/tools/shortest-path-certificate-check/versions/1.0.0/execute"}