fluctuations are of order at most $n/\log n$ [@benjamini_kalai_schramm; @benaim_rossignol] and are conjectured to be of order $t^{2/3}$. They can be larger and of order $n$ for modifications of $\mathbb Z^2$ known as thin cylinders [@chatterjee_dey].

The scaling of $t^{2/3}$ for the variance is conjectured for many additional interface growth models and is related to the Kardar-Parisi-Zhang equation [@amir_corwin_quastel; @krug_spohn; @sasamoto_spohn].

The constrained first passage percolation problem is a discrete analog to Hamilton-Jacobi equation. The large time behaviors of its solutions are extensively studied and homogenization results are obtained for a class of Hamiltonians [@scott_hung_yifeng_2014; @souganidis_1999; @krv]. Fluctuations in dimension one are of order $t$ [@rezakhanlou_clt] while in higher dimensions they are of lower order although only the logarithmic improvement to the bound has been achieved so far [@matic_nolen].

Example
=======

Before providing a more formal description of the algorithm we will illustrate the main ideas on one concrete example of a graph. Consider the following graph that has $12$ vertices labeled as $1$, $2$, $\dots$, $12$. The set $A$ contains the vertices $1$, $2$, and $3$, and the set $B$ contains only the vertex $12$. We want to find the shortest path from $A$ to $B$ subject to the 