{"id":"shortest-path-potential-check","version":"1.0.0","description":"Check claimed single-source shortest-path distances against a weighted digraph: edge inequalities and attainment.","supported_operations":["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"],"unsupported_operations":["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"],"semantics":["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\"."],"limits":{"max_vertices":500,"max_edges":2000,"max_id_bytes":64,"max_integer_digits":40,"max_distance_entries":500},"pricing":{"status":"unpriced","charge_usd":null},"input_schema":{"type":"object","additionalProperties":false,"required":["graph","source","distances"],"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},"distances":{"type":"array","maxItems":500,"items":{"type":"object","additionalProperties":false,"required":["vertex","distance"],"properties":{"vertex":{"type":"string","minLength":1,"maxLength":64},"distance":{"type":["string","null"],"pattern":"^(0|-?[1-9][0-9]*)$"}}}}}},"output_schema":{"type":"object","additionalProperties":false,"required":["valid","reason","first_discrepancy","reference_version"],"properties":{"valid":{"type":"boolean"},"reason":{"type":["string","null"],"enum":[null,"unknown_vertex","duplicate_vertex","missing_vertex","source_distance_not_zero","unreachable_mark_contradicted","edge_not_relaxed","distance_not_attained"]},"first_discrepancy":{"type":["object","null"],"additionalProperties":false,"required":["field","index","vertex","edge_id","expected","actual"],"properties":{"field":{"type":"string","enum":["source","distances","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"]}}},"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","distances":[{"vertex":"s","distance":"0"},{"vertex":"t","distance":"8"},{"vertex":"x","distance":"9"},{"vertex":"y","distance":"5"},{"vertex":"z","distance":"7"}]},"output":{"valid":true,"reason":null,"first_discrepancy":null,"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","distances":[{"vertex":"s","distance":"0"},{"vertex":"t","distance":"8"},{"vertex":"x","distance":"13"},{"vertex":"y","distance":"5"},{"vertex":"z","distance":"7"}]},"output":{"valid":false,"reason":"edge_not_relaxed","first_discrepancy":{"field":"graph.edges","index":2,"vertex":"x","edge_id":"tx","expected":"9","actual":"13"},"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","distances":[{"vertex":"s","distance":"0"},{"vertex":"t","distance":"8"},{"vertex":"x","distance":"8"},{"vertex":"y","distance":"5"},{"vertex":"z","distance":"7"}]},"output":{"valid":false,"reason":"distance_not_attained","first_discrepancy":{"field":"graph.vertices","index":2,"vertex":"x","edge_id":null,"expected":null,"actual":"8"},"reference_version":"clrs-4e-2022-ch22-single-source-shortest-paths"}}],"execute_url":"/v1/tools/shortest-path-potential-check/versions/1.0.0/execute"}