AI Glossary / Graphs and symbolic AI / Beginner
Path
Definition
A path is an ordered sequence of connected locations, nodes or states. In AI search, it describes successive states linked by available actions. In graph terminology, conventions vary: a simple path does not repeat vertices, while some AI texts use “path” more broadly for a sequence that may revisit a state.
What it means
A path records how one point is reached from another, not just the endpoints. In a directed graph, each step must follow an edge in its permitted direction. In an undirected graph, an edge can be traversed either way.
The nodes need not be physical places. They can represent configurations of a puzzle, stages of a workflow or states of a software system. Edges then represent legal transformations or relationships rather than roads.
A path's length often means its number of edges. Its cost can instead be the sum of travel times, prices, energy requirements or another specified weight. A path with fewer steps can therefore cost more than a longer one.
How it works
Start with an ordered list of nodes and verify that every consecutive pair has the required connecting edge. For a directed path, verify the edge's orientation. If the problem requires a simple path, also check that no vertex repeats.
For AI state-space search, each transition should correspond to an applicable action in the model. A sequence of plausible state labels is not enough if the intervening actions are unavailable or their prerequisites fail.
Algorithms can store parent pointers to reconstruct a discovered path. A search tree may contain different nodes representing the same domain state reached through different histories. The path retains that history even when the endpoint is identical.
When several edges connect the same pair of nodes, a node list alone may not identify which action or edge was used. Keep edge identifiers or action labels when they affect cost or meaning.
Three practical examples
- A navigation system returns the ordered road segments connecting an origin to a destination.
- A puzzle solver records legal moves from an initial arrangement to a goal arrangement.
- A workflow analyzer traces a sequence of transitions leading to a particular completion or failure state.
Think of it this way
Think of directions that say “start at reception, pass the courtyard, then enter the archive.” The order and the connections matter; merely naming reception and the archive does not describe a route.
The analogy is limited because a graph path can represent abstract operations, and physical details such as door width or temporary closures may be absent from the graph. A valid path in the model is only as applicable as its modeled connections.
Worked example
Consider an invented directed graph with edges S→G of cost 10, S→A of cost 2, A→B of cost 2 and B→G of cost 2. There are no other edges.
The path [S,G] has one edge and cost 10. The path [S,A,B,G] has three edges and cost 6. The first is shortest by edge count; the second is cheapest by the stated weights. Both include their starting and ending nodes.
The sequence [G,B,A,S] is not a directed path in this graph because the reverse edges do not exist. The sequence [S,B,G] also fails because S→B is missing.
The one-node sequence [S] is a zero-edge path under the common convention used here. It reaches the goal only if S itself satisfies the goal condition. These examples distinguish sequence length, graph connectivity, direction, cost and goal satisfaction.
Illustrative case study
The fictional Alder Routing team displays a route with fewer connections as “shortest.” Users assume this means fastest, but the program has treated every edge as having equal weight.
Alder specifies whether the request minimizes hops, distance or estimated time and connects the selected objective to the edge weights. It also stores the actual transitions so that different services between the same locations are not confused.
This fictional case shows why a technically valid path can still answer the wrong question. The route representation, direction rules and optimization objective must agree with the user's intent.
Common misconceptions and mistakes
- Any list of nodes is a path. Consecutive nodes must be connected as required by the graph.
- Reversing a path always gives another valid path. That need not hold in a directed graph.
- The fewest edges means the lowest cost. Edge weights can change which route is preferred.
- Every path solves the search problem. It must start appropriately and reach a state satisfying the goal.
- Path and simple path have one universal convention. State whether repeated vertices are allowed in the context being used.
Business use
Paths help explain how a system reached a result and what actions would connect a current situation to a target. They are useful in navigation, dependency analysis, workflow troubleshooting and symbolic problem solving.
A review should identify what nodes and edges mean, whether direction matters, and which quantity is minimized. Check how unavailable edges, changing costs and multiple transitions between the same nodes are handled.
For decision support, retain enough detail to reproduce the route and its cost. A screenshot of endpoints or an unexplained node list may omit the action choices needed to execute or audit it. If the graph is an abstraction, state which real-world constraints are outside its scope.
People also ask
Can a path contain just one node?
Yes, under a common convention it is a path with zero edges.
Can there be several shortest paths?
Yes. Different sequences can have equal minimum length or cost under the chosen objective.
Is a path the same as a trajectory?
A trajectory usually includes time or motion information in addition to the route or configurations. A path alone may not specify when each point is reached.
Check your understanding
Why is [S,A,B,G] preferable to [S,G] when minimizing cost in the worked example?
Answer: Its three edge costs sum to 6, while the direct edge costs 10. The route has more steps but a smaller total weight.
Related terms
- Node
- Directed graph
- Walks
- Simple Paths
- Shortest Paths
- Search tree
- Trajectory
- edge
- walk
- simple path
- path cost
- shortest path
Learn next
Draw a small directed weighted graph. Validate several node sequences, count their edges and sum their weights. Include a reverse sequence and a one-node sequence, then explain which ones solve a chosen start-to-goal problem.
More in Graphs and symbolic AI
- Partial solution - A partial solution is an intermediate candidate that specifies some, but not all, of what is needed to solve a problem.
- Particle MCMC - Particle MCMC is a family of Monte Carlo methods that combines particle-based sequential simulation with Markov chain Monte Carlo to sample from difficult...
- Passive learning - Passive learning, in the reinforcement-learning sense used here, means learning about the value or consequences of following a fixed policy.
- Path planning - Path planning is the process of finding a feasible route from a starting configuration to a goal configuration while respecting obstacles and relevant...
- Pattern matching - Pattern matching is the process of checking whether data fit a specified form and, where supported, extracting values from matching parts.
- Payoff function - A payoff function assigns a numerical value to an outcome or combination of players' actions, representing how desirable it is to a particular player.
Sources
The AIMA search chapter explains paths through state spaces and action costs: https://aima.cs.berkeley.edu/4th-ed/pdfs/newchap03.pdf
NetworkX specifies simple-path and shortest-path conventions: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.simple_paths.is_simple_path.html and https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.generic.shortest_path.html
The directed graph and Alder Routing case are original examples. This entry distinguishes broad AI usage from stricter simple-path terminology.
Previous: Password fatigue Next: Path analysis (statistics)