This paper presents an optimal dynamic programming algorithm, the first such algorithm in the literature to solve the shortest path problem with time windows and additional linear costs on the node service start times. To optimally solve this problem we propose a new dynamic programming algorithm which takes into account the linear node costs. This problem has numerous applications; two examples are job-shop scheduling and aircraft routing and scheduling. To underline the efficiency of the proposed method we compare it with an approach based on partial discretization of the time windows. It clearly outperformed the discretization approach on test problems with wide time windows and many nodes with negative costs.