Widely recognized as an excellent solution of global warming and oil crisis, electric vehicles (EVs) however suffer remarkable weakness such as the limited cruise range, which can be partly addressed by introducing en-route charging navigation systems. Different from traditional navigation, which solves a shortest path problem, the en-route charging navigation resorts to a joint charging and routing optimization. In this paper, we formulate the en-route charging navigation in a dynamic programming (DP) setting in both a deterministic and a stochastic traffic network. Specifically, to relieve computational complexity in navigation systems, a simplified charge-control (SCC) algorithm is presented in the deterministic case, which can simplify the charging control decisions within an SCC set. In the stochastic case, an online state recursion (OSR) algorithm is designed, which can provide an accurate navigation utilizing online information. Numerical simulation verifies the computing burden and accuracy of the proposed algorithms in a deterministic and a stochastic networks.