We propose a new parallel algorithm for the single-source shortest-path problem (SSSP). Its heap data structure is particularly advantageous on graphs with a moderate number of high degree nodes. On arbitrary directed graphs with n nodes, m edges and independent random edge weights uniformly distributed in the range [0,1] and maximum shortest path weight the PRAM version of our algorithm runs in average-case time using operations where |V _i| is the number of graph vertices with degree at least 2ⁱ. For power-law graph models of the Internet or call graphs this results in the first work-efficient o(n ^1/4) average-case time algorithm.