The problem of finding all shortest paths in a non-negatively weighted directed graph is addressed, and a number of new algorithms for solving this problem on a graph of n vertices and m edges are given. The first of these requires in the worst case min { 2mn, nᶟ } + O(n²˙⁵ ) addition and binary comparisons on path and edge costs, improving the previous bound (Dantzig, 1960) of n³ + O(n²logn) operations in a computational model where addition and comparison are the only operations permitted on path costs. The second algorithm presented, and the main result of this thesis, has an expected running time of O(n²logn) on graphs with edge weights drawn from an endpoint independent probability distribution, improving asymptotically the previous bound (Bloniarz, 1980) of O(n²lognlog*n), and resolving a major open problem (Bloniarz, 1983) concerning the complexity of the all pairs shortest path problem. Some variations on the new algorithm are analysed, and it is shown that two superficially good heuristics have a bad effect on the running time. A third variation reduces the worst case running time to O(nᶟ), making the method competitive with the O(nᶟ) classical algorithms of Dijkstra (1959) and Floyd (1962). The new algorithm is not just of theoretical interest - experimental results are given that show the algorithm to be fast for operational use, running an order of magnitude faster than the algorithms of Dijkstra and Floyd. The closely linked problem of distance matrix multiplication is also investigated, and a number of fast average time distance matrix multiplication algorithms are given.