Given an undirected graph $G$ and two pairs of vertices $(s_1, t_1), (s_2, t_2)$, the disjoint paths problem (DPP) asks for two vertex-disjoint paths, one from $s_1$ to $t_1$ and the other from $s_2$ to $t_2$. The problem has been shown to be in $P$ even for the generalization with $k$ disjoint paths, where $k$ is a constant [1, 2].I'm interested in practical algorithms to solve this problem. The algorithm given in [1] runs in $\mathcal{O}(nm)$ but uses many case distinctions which makes it very cumbersome to implement.Are there any known algorithms which are more practical to implement, even at the expense of a worse runtime guarantee? I'm interested in application to 3D grid graphs, so results assuming planarity or low tree-width unfortunately do not help. [1]: Shiloach, Y. (1980). A polynomial solution to the undirected two paths problem. Journal of the ACM (JACM), 27(3), 445-456.[2]:  Robertson, N., & Seymour, P. D. (1995). Graph minors. XIII. The disjoint paths problem. Journal of combinatorial theory, Series B, 63(1), 65-110.
Practical algorithms for the disjoint paths problem
algorithms;graphs