Instead of calculating paths between all pairs of input vertices, each iteration could store all IDs of vertex pairs along all previously-traced paths. A new Dijkstra would then need only be run if the start and end vertices did not appear in this list. This would effectively be equivalent to implementing the Floyd-Warshall algorithm.

Extra efficiency could likely be gained by first calculating straight-line distances between all vertices (where possible, which may not always be the case), and running Dijkstra's on the vertex pairs as sorted in order of decreasing distance. Because distances would be calculated from each from vertex to all other vertices, these distances could be calculated as maximal pair-wise distances from each from vertex to all nominated to vertices.

The ultimate aim here would be to speed up flow aggregation, which is currently pretty slow compared, for example, to igraph::betweenness().