# Dynamic programming of cheapest cost in LaTeX

From How can I automate the generation of this dynamic-programming graph?, Jubobs helped develop a foreach scheme to draw the paths. I was wondering if LaTeX can find the cheapest path by implementing dynamic programming.

\documentclass{article}

\usepackage{tikz}

\newcounter{rowcount}
\newcounter{columncount}

\begin{document}
\begin{tikzpicture}[scale=2]
\begin{scope}[rotate=-45]
% rows
\foreach[count=\y from 0] \W in
{{7,8,6},{8,8,8},{6,9,7},{7,8,10}} % row-wise weights
{
\stepcounter{rowcount}
\foreach \w [count=\x, remember=\x as \lastx (initially 0)] in \W
\draw (\lastx,\y) -- (\x,\y)
node[above,pos=0.5] {\w};
}
% columns
\foreach[count=\x from 0] \W in
{{5,6,10},{7,10,5},{10,5,6},{7,9,11}} % column-wise weights
{
\stepcounter{columncount}
\foreach \w [count=\y, remember=\y as \lasty (initially 0)] in \W
\draw (\x,\lasty) -- (\x,\y)
node[above,pos=0.5] {\w};
}
\fill (0,0) circle (0.1em) node[below left] {A};
\fill ({\value{columncount}-1},{\value{rowcount}-1}) circle (0.1em) node[below right] {B};
\end{scope}
\end{tikzpicture}
\end{document}

1. Does LaTeX have this ability?
2. If it does, how is something like this done?
• To be honest, I'd get the shortest path in another programming language than TeX if I were you. – jub0bs Apr 18 '14 at 4:37
• @Jubobs I know that can be done. I was curious about LaTeX's abilities. – dustin Apr 18 '14 at 4:40
• @dustin Before we look for the ability of LaTeX or TeX, we must remember that LaTeX/TeX is not programming language per se, though some programming is definitely possible, which makes it powerful. It is a document preparation system. So, why make your life difficult trying to use a document preparation system which can be easily solved using a programming language? And once you have found the answer, why not use LaTeX for beautiful presentation of your results? – Masroor Apr 18 '14 at 4:48
• The sagetex package gives you the ability to tap into the Sage CAS. Shortest path is discussed here. Using the sagetex package would allow the calculations to be done during the LaTeX compilation rather than having to do work with a separate program "outside" of your tex document. Sagemath Cloud gives you the access to the Sage CAS without having to install it to your computer. – DJP Apr 18 '14 at 5:43
• So you expect quite some knowledge of nontrivial optimization schemes? – percusse Apr 18 '14 at 6:29