Can a simple path exist in a graph with cycles?

Yes. The restriction applies to the chosen route, not the entire graph.

Can two different simple paths share a node?

Yes. Each path must avoid repeating nodes within itself.

Is the route from a node to itself simple?

Under the NetworkX convention, the singleton node list is a simple path of length zero.

AI Glossary / Graphs and symbolic AI / Intermediate

Simple Paths

Definition

A simple path is a sequence of connected graph nodes in which no node appears more than once. In a directed graph, each step must follow the edge direction. The term describes the path's structure, not its length, cost, or quality; a simple path can be much longer than the shortest available route.

What it means

Graphs represent entities as nodes and relationships as edges. A path describes a route through those relationships. Requiring the route to be simple prevents revisiting a node along that particular route.
This is different from requiring the entire graph to contain no cycles. A cyclic graph can contain many simple paths. It is also different from an edge-simple trail, which avoids repeating edges but may revisit nodes. Stating the convention matters because informal uses of “path” vary. Here the definition follows NetworkX: no repeated nodes, with a one-node, zero-edge path permitted from a node to itself.

How it works

To enumerate simple paths, a search can extend a partial route along outgoing edges while remembering which nodes are already on that route. It rejects an extension to an already visited node. On reaching the target, it reports the route, then backtracks to explore alternatives.
The visited set belongs to the current route, not necessarily to the whole enumeration. Otherwise, finding one path through a node could incorrectly prevent another valid path through the same node. A cutoff can limit the number of edges in returned paths. Even with efficient generation, the number of results can grow very quickly.

Three practical examples

A dependency analyst can list routes between two components that do not revisit any component along a route.
A network-planning exercise can examine alternative loop-free routes between a source and destination.
A process-model review can enumerate nonrepeating status sequences within a small graph and a chosen step limit.

Think of it this way

Think of walking between two places while refusing to visit the same junction twice. Different walks can still share a junction; the restriction applies separately to each route. The analogy is limited because graph edges may represent permissions or dependencies rather than roads, and a graph route may omit timing or capacity constraints.

Worked example

Consider an original directed graph with edges S→A, S→B, A→B, B→A, A→T, and B→T. There are four simple paths from S to T: S - A - T, S - B - T, S - A - B - T, and S - B - A - T.
Their lengths are 2, 2, 3, and 3 edges. A cutoff of 2 therefore retains only the first two. The sequence S - A - B - A - T is a valid directed walk but is not a simple path, because A occurs twice. Notice that the graph itself contains the directed cycle A→B→A; this does not invalidate its simple paths.
Now assign costs S→A = 2, S→B = 1, A→B = 1, B→A = 1, A→T = 5, and B→T = 10. The four path costs are respectively 7, 11, 13, and 7. The three-edge path S - B - A - T ties the two-edge path S - A - T for minimum total cost. Thus edge count and weighted cost answer different questions.
If S→A has two parallel edges in a multigraph, each usable as a distinct connection, then paths beginning with that transition have two edge-level realizations. An enumerator can return the same node sequence multiple times to represent these choices. Decide whether the application counts distinct node sequences or distinct edge combinations.

Illustrative case study

In a fictional case, Elm Systems reviews connections between an input service and an archive. The team initially asks for every simple path in a large dependency graph. The result count becomes difficult to inspect.
Analysts clarify that they only need routes with at most four edges and then examine a smaller relevant subgraph. They also distinguish parallel links that represent different connection types. The exercise shows why “all routes” needs a precise operational definition and manageable scope. It does not imply that simple-path enumeration alone proves the system is reliable.

Common misconceptions and mistakes

Simple does not mean shortest, cheapest, or easy to compute in bulk. It only excludes repeated nodes. A path's length usually counts edges; a node list containing four nodes has three edges.
Do not use a global visited set from ordinary reachability search without considering the enumeration task. Do not assume that a generator makes an enormous output set cheap: it can reduce the need to store all results at once while still taking substantial time to produce them. In a directed graph, an edge in the opposite direction cannot be traversed unless a corresponding forward edge exists.

Business use

For business graph analysis, first decide whether the need is reachability, one route, a cheapest route, a limited number of alternatives, or all simple paths. These are different requests with different computational costs.
If full enumeration is appropriate, specify source, target, allowed edge types, maximum length, and treatment of parallel edges. Check connectivity when useful, constrain the relevant graph, and record any cutoff in the report. A list restricted to four edges must not be described as an exhaustive list of all possible paths without qualification.

Check your understanding

Why does S - A - B - A - T fail the definition even if every indicated edge exists?

Answer: It visits node A twice. Valid adjacency alone is insufficient for simplicity.

Related terms

Learn next

Remove edge B→A from the example. The remaining simple S-to-T paths are S - A - T, S - B - T, and S - A - B - T. Explain why removing one directed edge eliminates only the path that needs that direction.

Sources

Sources: NetworkX official documentation, all_simple_paths, definition, edge-count cutoff, enumeration behavior and parallel edges: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.simple_paths.all_simple_paths.html .

Previous: Simple linear regression Next: Simple Random Sampling