The non-additive shortest path (NASP) problem asks for finding an optimal path that minimizes a certain multi-attribute nonlinear cost function. In this paper, we consider the case of a non-linear convex and non-decreasing function on two attributes.We present an efficient polynomial algorithm for solving a Lagrangian relaxation of NASP. We also present an exact algorithm that is based on new heuristics we introduce here, and conduct a comparative experimental study with synthetic and real-world data that demonstrates the quality of our approach.