Well, let's see...A simple bound can be trivially computed by running Dijkstra's on all nodes. Since Dijkstra is typically implemented in O(n log n + e) and we need to run this on all nodes, we'd get O(n^2 log n + e) which if the graph is dense rounds up to O(n^3).

Can this bound be improved upon? I seem to remember that Floyd-Warshall is also running in O(n^3), so the answer is "maybe". I would guess that the answer depends on what are the most recent advances in data structures.

What would you need this implementation for? Social network analysis? How sparse is the network?

I am totally aware of Dijkstra's algorithm and the question is for more modern algorithms, possibly those that are simple enough to actually get implemented.

Yes, I am thinking of sparse networks, in which m is in O(n). Here, Dijkstra is dominated by the O(n^2 log n) term and the question is whether there is an algorithm that performs better than that. I also know the wikipedia page suggested by Patrick, but the question is whether there are more recent advances on that topic.

Btw: I do not need any implementations. I am currently working on some algorithm for that and would like to publish it in the near future.

I think the problem of finding a sub-cubic all-pairs shortest pair is open, so it's doubtful that you'll beat O(n^2 log n) with a "simple" implementation.

On the other hand, if you want to squeeze extra performance you attack the matrix multiplication that it is at the core of F-W. If I remember correctly, the best bound for matrix multiplication is somewhere around O(n^2.4), so it is possible to get some extra performance out.

Look up Uri Zwick's papers on the subject - I think he has proved a running time of O(C*n^2.4) where C is the maximum edge weight, assumed integer.

You can think Genetic algorithm or Fuzzy approach for this u can find lot of works on this area

@Mihai, thanks for the helpful response. I have developed an algorithm in O(nm) - that is: for sparse networks it will be O(n^2) which is sub-cubic. There are - unfortunately - some constraints on the graphs such that this runtime is met - weights cannot be arbitrary high considered the diameter of the graph. Anyway, the algorithm is astonishingly simple, but the analysis is not... ;-)

Hello Katharina,

Getting to O(n^2) is probably the best you can do in general, since it's pretty trivial to show by a counting argument that for the all-pairs SP problem the lower bound has to be O(n^2) (a path from each node to every other node).

Does your network has any other special structure outside of sparsity? Your mentioning of the graph diameter probably means that you have a typical "hub-and-spoke" network with several power users (the hubs) to which cliques of users are connected directly, and the hubs are bridged? Also, since the size of the weight plays a role as well, that leads me to think you're perhaps rescaling the weights, iteratively? If that's the case, wouldn't you need a logW in your running time, where W = max{weights}? I did something similar for a survivable network design problem, where I based computing the distance on a max-flow procedure, with an artificial commodity with a supply and demand of one unit for each pair of nodes. And since max flow runs in O(mn)...

Have you tested the performance compared to Johnson's (repeated Dijkstra)? I assume you already proved optimality.

I'd be curious professionally to look at your work once you get it through the peer review process. Please keep in touch - you can find my contact info in my profile.

I think Viterbi algorithm can be used in this case. It is very efficient in finding the shorted path (best decoding hypothesis) in a huge weighted finite state transducer network in the speech recognition domain. This algorithm can be realized using the token passing paradigm.

There is a rather fast algorithm for the sparsed graphs of road networks. It will be published soon but yet in Russian only. I can send you russian text if that make sense.

@Airat, that sounds exciting! Unfortunately, I do not understand a word of Russian and do not know anyone who does and could possibly translate it. Is it your own paper? Any chance to turn it into an international publication?

Yes. Now I try to translate this paper through webshop.elsevier.com. If this service is good, I will place result on arxiv.org.

The paper in Russian have published. Here is a link: http://www.lib.tsu.ru/mminfo/000349342/19/image/19-084.pdf

To my regret elsevier.com can not translate the paper. Now I try to translate the paper by myself.

Yet you can see the table 2 ("таблица 2", last page) and compare speed.

The small legend:

Группа графов - Set of graphs

ДД - Dijkstra algorithm, binary heap implementation

БП - our algorithm

среднее время - average time

Среднее ускор. БП/ДД, раз - average speegup

I translated the article, as promised. Here is the link: http://arxiv.org/abs/1308.1568

Hi Katharina, I had the same question myself recently and did some searching. I didn't find anything better than the \tilde{O}(|G|^{2.376}) solutions described in the 90s. E.g.:http://dx.doi.org/10.1016/S0747-7171(08)80013-2 .

And of course, some of the "fastest" algorithms in terms of scaling may actually be slower than the well-known simpler algorithms when graphs are less than huge!