title: Compute costs only of paths between all pairs in weighted graph
body: <p>Is there an algorithm faster than O(n2) for computing the costs <strong>only</strong> between every pair in a weighted non-cyclic graph, assuming I do not need the shortest paths but just the paths I would get if using simple BFS? I do not need the actual paths, only the costs of the paths. My current solution is just to do a BFS starting from each node also keeping track of the weights of the edges along the way but this is obviously O(n2) and I am wondering if it is possible to do any better.</p>