The exact localization of the mandibular nerve with respect to the bone is important for applications in dental implantology and maxillofacial surgery. Cone beam computed tomography (CBCT), often also called digital volume tomography (DVT), is increasingly utilized in maxillofacial or dental imaging. Compared to conventional CT, however, soft tissue discrimination is worse due to a reduced dose. Thus, small structures like the alveolar nerves are even harder recognizable within the image data. We show that it is nonetheless possible to accurately reconstruct the 3D bone surface and the course of the nerve in a fully automatic fashion, with a method that is based on a combined statistical shape model of the nerve and the bone and a Dijkstra-based optimization procedure. Our method has been validated on 106 clinical datasets: the average reconstruction error for the bone is 0.5 +/- 0.1 mm, and the nerve can be detected with an average error of 1.0 +/- 0.6 mm.