We present two new linear algorithms for the single source shortest paths problem. The worst case running time of the first algorithm is O(m + C log C), where m is the number of edges of the input network and C is the ratio of the largest and the smallest edge weight. The pseudo-polynomial...