as graphic cards). Consequently, the output will not be sufficient to determine the exact minimizing path. The reconstruction of the minimizing path is possible with subsequent applications of the method, because the output can include the vertex $X\in B$ that is the endpoint of $\hat \pi$, the last edge $x$ on the path $\hat \pi$, and the value $F_2(\hat \pi)$. Once $X$ and $x$ are found, the entire process can be repeated for the graph $G'(V',E')$ with $$V'=V\setminus B,\quad A'=A, \quad B'=\{X\}, \quad\mbox{ and }\quad M'=F_2\left(\hat \pi\right)-f_2(x).$$ The result will be second to last vertex on the minimizing path $\hat \pi$. All other vertices on $\hat\pi$ can be found in the same way.

Although the algorithm works for general graphs and integer-valued functions $f$, its implementation on SIMD hardware requires the vertices to have bounded degree. This requirement is satisfied by subgraphs of $\mathbb Z^d$.

Finding the the length of the shortest path in graph is equivalent to finding the shortest passage time in first passage percolation. Each of the vertices in $A$ can be thought of as a source of water. The value $f_1(e)$ of each edge $e$ is the time it takes the water to travel over $e$. 