Skip to content

Commit 81d3750

Browse files
authored
Update breadth-first-search.md
Fixed naming for vertices variables to be consistent with the rest of the statement
1 parent 921fc8a commit 81d3750

1 file changed

Lines changed: 1 addition & 1 deletion

File tree

src/graph/breadth-first-search.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -154,7 +154,7 @@ the criterion is the condition $d_a [v] + d_b [v] = d_a [b]$.
154154

155155
* Find the shortest path of even length from a source vertex $s$ to a target vertex $t$ in an unweighted graph:
156156
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.
157-
Any edge $(a, b)$ of the original graph in this new column will turn into two edges $((u, 0), (v, 1))$ and $((u, 1), (v, 0))$.
157+
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))$.
158158
After that we run a BFS to find the shortest path from the starting vertex $(s, 0)$ to the end vertex $(t, 0)$.
159159

160160
## Practice Problems

0 commit comments

Comments
 (0)