After the newer and newer successes of neural networks in playing board games, one feels that the next goal we set could be something more useful than beating humans in Starcraft. More precisely, I wondered whether
Can neural networks be trained to solve classic algorithmic problems?
Here I mean that for example the network would get an input graph $G$ with weighted edges, and two vertices $s$ and $t$ specified, and we asked it to find a shortest $st$ path as fast as possible. Then I guess the neural network would discover and train itself to use Dijkstra or something similar.
On one hand, we know that the computational power of neural networks is $TC^0$. On the other, I don't know if this is necessarily related to my question. Even so, for most problems we don't know whether they can be solved in $TC^0$ or not. Seeing whether a neural network can train itself, might be a good indicator whether there's a fast algorithm or not. For example, if neural networks can't train themselves to solve SAT fast, then that makes it (even more) likely that $NP\not\subset TC^0$. I wonder what a neural network would do with GRAPHISOMORPHISM or FACTORIZATION.
Of course, extracting the algorithm is a whole different question. I suspect experts know how to do that, but discussing it is not the topic of this question.
Added two days later: After seeing the answers, let me specify that if you answer in the negative, then I would like to know
Why is playing chess easier than Dijkstra or Graphisomorphism?