Path in a square matrix I was given this question during an entry test for Computer Graphics course.
A graph with $n^2$ nodes is represented by a square matrix. From node $(i,j)$ there are edges to nodes $(i-1,j),(i+1,j),(i,j-1),(i,j+1)$ unless they exceed the board size. Some of the edges are yellow other are blue. Suggest an algorithm with $O(|V|^2)$ running time to detect if there is a non-cyclical path from node $A$ to node $B$ containing more blue than yellow edges.

If the blue edges cost -1, the yellow cost 1 and Bellman-Ford's shortest path from $A$ to $B$ is greater than or equal to 0 than there is no such path. Is this correct? It requires $O(|V|^2)$ time since $|E|=O(|V|)$
 A: I doubt that this is the intended solution, but you can find min-cost paths in the presence of negative cycles using minimum-weight perfect matching.
For the given graph $G$ construct a graph $G'$ such that
\begin{align}
V(G') &= \Big\{w_{\{u^3,v^0\}}, w_{\{u^2,v^1\}}, w_{\{u^1,v^2\}}, w_{\{u^0,v^3\}}\ \Big|\ \{u,v\} \in E(G)\Big\}, \\
E(G') &= \Big\{
    \big\{w_{\{u^3,v^0\}}, w_{\{u^2,v^1\}}\big\},\\
    &\qquad\big\{w_{\{u^2,v^1\}},w_{\{u^1,v^2\}}\big\}, \\
    &\qquad\big\{w_{\{u^1,v^2\}},w_{\{u^0,v^3\}}\big\}
    \ \Big|\ \{u,v\} \in E(G)\Big\}\\
    &\,\cup\!\!\bigcup_{u \in V(G)}\Big\{
      \big\{w_{\{u^3,x^0\}}, w_{\{u^3,y^0\}}\big\}
        \ \Big|\ \{u,x\} \in E(G), \{u,y\} \in E(G)\Big\}.
\end{align}
In other words, we make each edge $\{u,v\}$ into a path of length $3$, namely: $$w_{\{u^3,v^0\}} \leftrightarrow w_{\{u^2,v^1\}} \leftrightarrow w_{\{u^1,v^2\}} \leftrightarrow w_{\{u^0,v^3\}},$$
and vertices $w_{\{u^3,\bullet\}}$of $G'$ corresponding to a single vertex $u$ of $G$ we make into a small clique $K_{\deg_G(u)}$.

The weight/length of edge $\{u,v\}$ is put on edge $\big\{w_{\{u^2,v^1\}},w_{\{u^1,v^2\}}\big\}$ of $G'$.
Now, if you want to find the minimum weight path between $\alpha$ and $\beta$ in $G$, then add vertices $w'_\alpha$ and $w'_\beta$, together with edges $\{w'_\alpha, w_{\{\alpha^3,u\}}\}$ for any $u \in N(\alpha)$ and $\{w'_\beta, w_{\{\beta^3,v\}}\}$ for any $v \in N(\beta)$, and calculate the minimum weight perfect matching in that graph.
The minimum weight path in $G$ uses edge $\{u,v\}$ if and only if the edge $\big\{w_{\{u^2,v^1\}},w_{\{u^1,v^2\}}\big\}$ is used in the corresponding minimum-weight perfect matching. The algorithm of Gabow and Tarjan has complexity $\mathcal{O}\big(m\sqrt{n \log n}\log(nN) \big)$ where $N$ is the maximum integer edge weight, which in your case is well below the required $O(n^2)$ bound.
I hope this helps $\ddot\smile$
