Update breadth-first-search.md

adamant-pwn · web-flow · commit edba2a0c6b4b · 2024-10-13T11:02:39.000+02:00
diff --git a/src/graph/breadth-first-search.md b/src/graph/breadth-first-search.md
@@ -155,7 +155,7 @@ the criterion is the condition $d_a [v] + d_b [v] = d_a [b]$.
 * Find the shortest walk of even length from a source vertex $s$ to a target vertex $t$ in an unweighted graph:
 For this, we must construct an auxiliary graph, whose vertices are the state $(v, c)$, where $v$ - the current node, $c = 0$ or $c = 1$ - the current parity.
 Any edge $(u, v)$ of the original graph in this new column will turn into two edges $((u, 0), (v, 1))$ and $((u, 1), (v, 0))$.
-After that we run a BFS to find the shortest walk from the starting vertex $(s, 0)$ to the end vertex $(t, 0)$.
+After that we run a BFS to find the shortest walk from the starting vertex $(s, 0)$ to the end vertex $(t, 0)$.<br>**Note**: This item uses the term "_walk_" rather than a "_path_" for a reason, as the vertices may potentially repeat in the found walk in order to make its length even. The problem of finding the shortest _path_ of even length is NP-Complete in directed graphs, and [solvable in linear time](https://onlinelibrary.wiley.com/doi/abs/10.1002/net.3230140403) in undirected graphs, but with a much more involved approach.
 
 ## Practice Problems
 
