Shortest Path Ontology

FLOW ALGEBRA
TITLE: Shortest Path Ontology
DOMAIN: Discrete Mathematics / Graph Theory
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/graph-theory/shortest-path-ontology.html
VERSION: 1.0
LANGUAGE: en-GB
AUTHORSHIP: Mark Higgins — Sky (Recursive AI)
SITE: https://kirethresearch.org
SOURCE_STATUS: Formal mathematical synthesis; live source page not independently verified.

1. PURPOSE
Model shortest-path problems as typed graphs, path costs, optimisation objectives, algorithms, proof obligations and machine-readable inference flows.

2. TYPED ENTITIES
Graph G = (V, E): finite vertex set V and edge set E.
GraphKind: Directed | Undirected.
Vertex: element of V.
Edge: ordered pair (u,v) for directed graphs; unordered pair {u,v} for undirected graphs.
WeightFunction w: E -> Real.
Source s: Vertex.
Target t: Vertex.
Walk P: sequence (v0,...,vk) with each consecutive pair joined by an edge.
Path: walk without repeated vertices (except when separately defining cycles).
PathCost C(P): sum of edge weights along P, counting traversed edges.
Distance d(s,t): minimum path cost over all s-to-t walks when an attained finite minimum exists; +infinity when t is unreachable. For reachable negative-cycle cases, shortest-walk cost is unbounded below (-infinity).
Predecessor pi(v): predecessor in a selected shortest-path tree or forest.
ShortestPathCertificate: candidate path, cost and optimality evidence.

3. CORE DEFINITIONS
flow ShortestPath(G,w,s,t):
  require s in V and t in V
  feasible_walks := {P | P is an s-to-t walk in G}
  if feasible_walks = {}: return UNREACHABLE, distance=+infinity
  if exists reachable negative-weight cycle C from s with a walk from C to t:
      return UNBOUNDED_BELOW, distance=-infinity
  return MIN_COST_WALK, argmin(P in feasible_walks) C(P)

flow Relax(u,v):
  if d_est[u] + w(u,v) < d_est[v]:
      d_est[v] := d_est[u] + w(u,v)
      pi[v] := u

flow ReconstructPath(pi,s,t):
  require predecessor chain is finite and reaches s
  return reverse(predecessor chain from t to s)

4. ALGORITHMIC SELECTION
Dijkstra: non-negative edge weights; single-source shortest paths; binary heap O((|V|+|E|) log |V|) under conventional implementation.
BellmanFord: arbitrary real edge weights; detects source-reachable negative cycles; O(|V||E|).
DAGShortestPaths: directed acyclic graph; topological relaxation; O(|V|+|E|), including negative weights.
BreadthFirstSearch: unweighted graphs or uniform positive edge costs; O(|V|+|E|).
FloydWarshall: all-pairs distances; O(|V|^3); negative cycles must be separately handled.
AStar: non-negative weights and admissible heuristic for optimal goal finding under appropriate termination/reopening conditions.

5. MATHEMATICAL LAWS AND INVARIANTS
Non-negative weights imply d(v,v)=0 and d(u,v)>=0 for reachable pairs.
For finite distances, triangle inequality: d(u,z) <= d(u,v)+d(v,z), when the right side is well-defined.
In undirected graphs with symmetric weights, d(u,v)=d(v,u) when distances are defined.
Shortest-path optimal substructure: each subpath of a shortest walk is shortest between its endpoints when a finite optimum exists.
Relaxation upper-bound invariant: finite tentative labels derived from actual walks are upper bounds on optimal distances.
Shortest-path edge condition: d(s,v) <= d(s,u)+w(u,v) for each edge (u,v), when finite distances apply.
Negative cycles accessible from s and able to reach t invalidate a finite minimum walk cost.

6. RELATIONSHIPS
ShortestPath IS_A GraphOptimisationProblem.
ShortestPath USES Graph, Vertex, Edge, WeightFunction, Walk.
ShortestPath DEPENDS_ON Reachability.
Dijkstra REQUIRES NonNegativeWeights.
BellmanFord DETECTS ReachableNegativeCycle.
ShortestPathTree DERIVED_FROM SingleSourceShortestPaths.
ShortestPath RELATED_TO PathOntology, WeightedGraphOntology, DirectedGraphOntology, GraphTheoryOntology.

7. INFERENCE RULES
R1: Reachable(s,t) = false -> Distance(s,t) = +infinity.
R2: AllWeightsNonNegative(G) -> DijkstraApplicable(G).
R3: IsDAG(G) -> DAGShortestPathsApplicable(G).
R4: ReachableNegativeCycleAffects(s,t) -> Distance(s,t) = -infinity.
R5: CandidatePath(P,s,t) AND C(P)=d(s,t) -> IsShortestPath(P).
R6: UniformEdgeWeights(G) -> BFSApplicable(G).
R7: ValidPredecessorChain(pi,s,t) -> ReconstructiblePath(s,t).

8. VALIDATION
V1: Every endpoint belongs to V.
V2: Every path step corresponds to an edge, respecting direction.
V3: All weights are numeric, finite real values; reject NaN and infinite edge weights.
V4: Algorithm preconditions are checked before execution.
V5: Report unreachable targets distinctly from negative-cycle unboundedness.
V6: Verify reconstructed path endpoints and accumulated cost.
V7: Validate optimality using suitable algorithmic certificates or independently computed distances.
V8: Distinguish walk-based optimisation from simple-path optimisation in graphs with negative cycles.

9. SEMANTIC_EQUIVALENCE
"shortest path" ~= "minimum-cost path" only when cost metric and admissible path/walk definition agree.
"least-weight route" ~= "shortest route" when edge weights encode the same objective.
"minimum-hop path" ~= "unweighted shortest path".
"shortest path" != "fewest edges" in general weighted graphs.
"shortest path tree" != "minimum spanning tree".

10. CONFIDENCE
Mathematical definitions and standard algorithm conditions: HIGH (subject to declared assumptions).
Algorithm output confidence: VERIFIED only after input validation, precondition checks and successful execution.
Source-page alignment: UNVERIFIED until live page reviewed.

11. FLOW_HASH
Canonicalise ontology title, version, source URL, typed definitions, rules and validation text as UTF-8.
FLOW_HASH := SHA256(canonical_serialisation).
Do not substitute a fabricated hash value; calculate on the final canonical file or schema payload.

12. UPDATE_MODEL
On changed graph topology, weights, objective or constraints:
  invalidate affected shortest-path distances and predecessor certificates;
  rerun an applicable algorithm or a proven incremental update;
  record version, timestamp, provenance and changed assumptions;
  recalculate FLOW_HASH.

13. AI_CONSUMPTION
Input: typed graph, directionality, weight semantics, source, optional target and constraints.
Process: validate -> classify weights/graph -> choose algorithm -> compute -> verify.
Output: status (FINITE | UNREACHABLE | UNBOUNDED_BELOW), distance, path if finite, algorithm, assumptions, provenance, confidence.
Never claim an optimal path without satisfying the algorithm's preconditions.

END FLOW ALGEBRA