StPfade

StPfad or stPfade (s-t paths) is a concept in graph theory referring to a path that starts at a designated source vertex s and ends at a designated target vertex t. In an undirected graph, an stPfad is a sequence of vertices connected by edges from s to t with no repeated vertices. In a directed graph, the edges along the path must be oriented from each vertex to the next. The length of an stPfad is typically the number of edges, while a weighted path has a total weight equal to the sum of the edge weights.

Existence and basic properties: An stPfad exists between s and t if t is reachable from s (undirected graphs) or if there is a directed path from s to t (directed graphs). The set of all stPfade from s to t is often denoted P(G, s, t). Counting or listing all such paths can be computationally difficult; counting all simple stPfade is a hard problem in general.

Connectivity and disjoint paths: The study of stPfade is closely tied to connectivity. The maximum number of internally vertex-disjoint stPfade corresponds to the vertex connectivity between s and t (as stated by Menger’s theorem). Similarly, the maximum number of edge-disjoint stPfade relates to edge connectivity and ties into the max-flow min-cut framework.

Algorithms and computation: To find a single stPfad, breadth-first search yields a shortest unweighted path, while Dijkstra’s algorithm finds a shortest weighted path. In directed acyclic graphs, dynamic programming can count or enumerate stPfade efficiently. Enumerating all stPfade is typically exponential in size; specialized algorithms exist for generating the k shortest simple stPfade (for example, Yen’s and Eppstein’s algorithms).

Applications: StPfade underpin routing, network design and reliability analysis, circuit layout, and various problems in transport and communication networks where establishing a viable connection from s to t is essential.