Open problems on the frontiers of TCS
Here are three in shortest paths research:

$1$. Is there a linear time algorithm for single source shortest paths in directed graphs with nonnegative weights, at least in the word-RAM model of computation? Note that a linear time algorithm exists for undirected graphs (see Thorup's paper). Based on that, Hagerup has a runtime of $O(n+m\log w)$ for directed graphs with weights bounded by $2^w$. Is there a faster algorithm?

$2$. Is there an $O(n^\omega$ polylog $n)$ algorithm for all pairs shortest paths in unweighted directed graphs? ($\omega&lt;2.376$ is the exponent of matrix multiplication) The current best runtime is $O(n^{2.575})$ by Zwick, and for undirected graphs the problem can be solved in $O(n^\omega$ polylog $n)$. 

(Are the directed problems actually harder?)

$3$. Is there an $O(n^{2.9})$ algorithm for all pairs shortest paths in $n$-node graphs with weights in {$0,\ldots,n$}? Or, is there a reduction from the general all pairs shortest paths problem to this restriction?