Summary: We consider parallel shortest-paths computations in weighted undirected graphs \(G=(V,E)\), where \(n=|V|\) and \(m=|E|\). The standard \(O(n^3)\) work path-doubling (Floyd-Warshall) algorithm consists of \(O(\log n)\) phases, where in each phase, for every triplet of vertices \((u_1, u_2, u_3) \in V^3\), the distance between \(u_1\) and \(u_3\) is updated to be no more than the sum of the previous-phase distances between \(\{u_1, u_2\}\) and \(\{u_2, u_3\}\). We introduce a new \({\mathcal N} {\mathcal C}\) algorithm that for \(\delta =o(n)\), considers only \(O(n \delta^2)\) triplets. Our algorithm performs \(\widetilde O(n \delta^2)\) work and augments \(E\) with \(\widetilde{O}(n \delta)\) new weighted edges such that between ever pair of vertices, there exists a minimum weight path of size (number of edges) \(\widetilde O(n/ \delta)\) (where \(\widetilde O(f) \equiv O(f\) polylog \(n))\). To compute shortest-paths, we apply to the augmented graph algorithms that are efficient for small-size shortest paths. We obtain an \(\widetilde O(t)\) time \(\widetilde O(|S|n^2 +n^3/t^2)\) work deterministic PRAM algorithm for computing shortest-paths from \(|S|\) sources to all other vertices, where \(t\leq n\) is a parameter. When the ratio of the largest edge weight and the smallest edge weight is \(n^{O (\text{polylog} n)}\), the algorithm computes shortest paths. When weights are arbitrary, it computes paths within a factor of \(1+n^{-\Omega (\text{polylog} n)}\) of shortest.