We show how to exploit graph sparsity in the \FW algorithm for the all-pairs shortest path (\APSP) problem. \FW is an attractive choice for \APSP on high-performing systems due to its structural similarity to solving dense linear systems and matrix multiplication. However, if sparsity of the input graph is not properly exploited, \FW will perform unnecessary asymptotic work and thus may not be a suitable choice for many input graphs. To overcome this limitation, the key idea in our approach is to use the known algebraic relationship between \FW and Gaussian elimination, and thereby import several algorithmic techniques from sparse Cholesky factorization, namely, fill-in reducing ordering, symbolic analysis, supernodal traversal, and elimination tree parallelism. When combined, these techniques reduce computation, improve locality, and enhance parallelism. We implement these ideas in an efficient shared memory parallel prototype that is orders of magnitude faster than a baseline \FW that does not exploit sparsity. Our experiments suggest that \FW algorithm can be competitive with Dijkstra’s algorithm (the algorithmic core of Johnson’s algorithm) for several classes sparse graphs.