The Richest Path Problem is a variation of a classical linear program, that can be stated as

$(max{\displaystyle \underset{(n_1)}{\overset{?}{}}},n_{2}inA{v}_{n_1,n_2}*x_{n_1,n_2}$

Such that

$({\displaystyle \underset{(n)}{\overset{?}{}}},n_{\text{d}\text{e}\text{s}\text{t}}inA{x}_{n,n_{\text{d}\text{e}\text{s}\text{t}}}=1$

$0x_{n_1,n_2}1$ for all $(n_1,n_2)inA$

in which $G=(N,A)$ is a network graph consisting of a set of nodes $N,$ and a set of arcs AsubN$N$ that connect the nodes, such that $(n_1,n_2)inA$ implies that the network includes an arc $(n_1,n_2)$ that directly connects node $n_1$ to node $n_2.$ In particular, the left summation in the connectivity constraint is over $(n^{\text{'}},n)inA$ for the node $n$; the summation therefore considers all the incoming arcs from nodes $n^{\text{'}}$inN that enter node $n.$ Similarly, the right summation, which is over $(n,n^{\text{'}})inA,$ considers all the outgoing arcs emanating from the node $n.$ The decision variables within the preceding linear program $x_{n1n2}$ for $(n_1,n_2)inA$ are such that $x_{n1n2}=1$ implies that $(n_1,n_2)$ is included in the path that is selected to traverse from the origin node $n_{\text{o}\text{r}\text{i}\text{g}}$ to the destination node $n_{\text{d}\text{e}\text{s}\text{t}}.$ The beneficial value of including $(n_1,n_2)$ within the path is expressed as $v_{n1n2},$ and the linear program is thus to construct the path from $n_{\text{o}\text{r}\text{i}\text{g}}$ to $n_{\text{d}\text{e}\text{s}\text{t}}$ that incurs the maximal total benefit, i$.$e$.$ the richest path.

The Richest Path Problem $($a$.$k$.$a$.$ the "Longest Path Problem"$)$ is related to the Lerch$-$Grossman $($LG$)$ algorithm used in the context of open$-$pit mining, to determine the final pit. In a rough sense, the LG algorithm is to carve out a path into the earth and return to the surface, having excavated the optimally richest combination of ore and waste rock.

a$)$ Consider the following network graph $G=(N,A),$ in which $N=\{n_{\text{o}\text{r}\text{i}\text{g}},a,b,c,d,e,n_{\text{d}\text{e}\text{s}\text{t}}\}$ and $A=\{(n_{\text{o}\text{r}\text{i}\text{g}},a),(n_{\text{o}\text{r}\text{g}},b),(a,b),(a,c),(a,d),(b,e),(b,n_{\text{d}\text{e}\text{s}\text{t}}),(c,e),(d,e),(d,n_{\text{d}\text{e}\text{s}\text{t}}),(e,n_{\text{d}\text{e}\text{s}\text{t}})\}$; the numbers written along each arc $(n_1,n_2)$ corresponds to the values $v_{n1n2}.$