<h1>Defining Path</h1>

<p>You are right to be confused if your professors did not clarify (see warning at end). The term "path" can mean a few things:</p>

<p><strong>"Concrete" Path</strong>:
Recall, a graph is a collection of vertices and edges. A path on the graph is then:</p>

<p><span class="math-container">$$v_1\xrightarrow{e_1} v_2\xrightarrow{e_2} \cdots \xrightarrow{e_{n-1}} v_n$$</span></p>

<p>Where <span class="math-container">$v_i$</span> are vertices on the graph and the arrows denote the direction traversed over the undirected edges <span class="math-container">$e_j$</span>. Observe, this definition explicitly defines some "chain" of vertices connected by specific edges. </p>

<p><strong>"Abstract" Path</strong>: Say there is some task that involves a serious of repeated <em>actions</em> but does not depend on specific objects. We can define this as a chain of composed functions:</p>

<p><span class="math-container">$$f_n\circ\cdots \circ f_1$$</span></p>

<p>The idea, is that this definition is little more abstract. Though, there are many other ways one could define "path."</p>

<h1>"Solution Path"</h1>

<p><strong>A Subtlety</strong></p>

<blockquote>
  <p>So, in this case, is the solution path A -> B -> C, i.e. the order in which the nodes are visited? Or is the solution path A -> B -> A -> C? Basically saying that we go from A to B, but to go from B to C, we must go through A again.</p>
</blockquote>

<p>BFS does not "go through A again." Considering you are using a queue based implementation, once A has been visited there will be no need to "visit" it again. That is, we have added all nodes we need to the queue and marked A as being seen. This leads into:</p>

<blockquote>
  <p>How to report the solution path of a search algorithm on a graph?</p>
</blockquote>

<p>Since, these algorithms do not revisit nodes, what is <strong>most likely</strong> being asked of you is for you to report the order of the visits - this is what my professors wanted in my AI &amp; Algorithms courses.</p>

<p><strong>A Warning</strong>: I can only answer what <em>my professors</em> wanted. Please clarify this with your instructors. </p>

CC BY-SA 4.0
2020-02-09T20:04:10.183Z
2020-02-09T20:12:36.630Z
2020-02-09T20:12:36.630Z
respectful
<p>I'm working on a problem where we are given a graph and asked to perform various search algorithms (BFS, DFS, UCS, A*, etc.) and the goal state is to visit all nodes in the graph. After all nodes are visited, we need to print out the "solution path." However, I am a bit confused on what "path" means in AI. </p>

<p>For simplicity, let's just consider a graph of 3 nodes: A, B and C with 2 undirected edges (A, B) (A, C). If we perform BFS on this graph starting at node A and traversing alphabetically, we'd visit A, then B, then C.  So, in this case, is the solution path <code>A -&gt; B -&gt; C</code>, i.e. the order in which the nodes are visited? Or is the solution path <code>A -&gt; B -&gt; A -&gt; C</code>? Basically saying that we go from A to B, but to go from B to C, we must go through A again. </p>

<search><path-planning><path-finding>
How to report the solution path of a search algorithm on a graph?
anonuser01
# How to report the solution path of a search algorithm on a graph?

(Asked by: username_0 on 2020-02-08)

I'm working on a problem where we are given a graph and asked to perform various search algorithms (BFS, DFS, UCS, A\*, etc.) and the goal state is to visit all nodes in the graph. After all nodes are visited, we need to print out the "solution path." However, I am a bit confused on what "path" means in AI.

For simplicity, let's just consider a graph of 3 nodes: A, B and C with 2 undirected edges (A, B) (A, C). If we perform BFS on this graph starting at node A and traversing alphabetically, we'd visit A, then B, then C. So, in this case, is the solution path `A -> B -> C`, i.e. the order in which the nodes are visited? Or is the solution path `A -> B -> A -> C`? Basically saying that we go from A to B, but to go from B to C, we must go through A again.

**Tags:** search, path-planning, path-finding


---

## 1 answers

### Answer by username_1 on 2020-02-09. Score: 1

# Defining Path

You are right to be confused if your professors did not clarify (see warning at end). The term "path" can mean a few things:

**"Concrete" Path**:
Recall, a graph is a collection of vertices and edges. A path on the graph is then:

$$v\_1\xrightarrow{e\_1} v\_2\xrightarrow{e\_2} \cdots \xrightarrow{e\_{n-1}} v\_n$$

Where $v\_i$ are vertices on the graph and the arrows denote the direction traversed over the undirected edges $e\_j$. Observe, this definition explicitly defines some "chain" of vertices connected by specific edges.

**"Abstract" Path**: Say there is some task that involves a serious of repeated *actions* but does not depend on specific objects. We can define this as a chain of composed functions:

$$f\_n\circ\cdots \circ f\_1$$

The idea, is that this definition is little more abstract. Though, there are many other ways one could define "path."

# "Solution Path"

**A Subtlety**

> So, in this case, is the solution path A -> B -> C, i.e. the order in which the nodes are visited? Or is the solution path A -> B -> A -> C? Basically saying that we go from A to B, but to go from B to C, we must go through A again.

BFS does not "go through A again." Considering you are using a queue based implementation, once A has been visited there will be no need to "visit" it again. That is, we have added all nodes we need to the queue and marked A as being seen. This leads into:

> How to report the solution path of a search algorithm on a graph?

Since, these algorithms do not revisit nodes, what is **most likely** being asked of you is for you to report the order of the visits - this is what my professors wanted in my AI & Algorithms courses.

**A Warning**: I can only answer what *my professors* wanted. Please clarify this with your instructors.


---

