All pairs shortest path with maximum distance I didn't succeed to find an algorithm that finds the shortest path in a weighted non directed graph between all pairs of nodes whose shortest path distance are inferior to a specific number. I think that, especially if the maximum distance is very small, it should significantly improve my algorithm's performance. Do you know such an algorithm ?
For example : let's say I set a maximum distance of 30. If the shortest path between A and B is 10, I want the algorithm to find it (and provide me the distance). If the shortest path between B and C is 50, I don't want the algorithm to find it.
Thanks,
 A: Interpreting your question that you want to find the shortest paths in order of increasing length, then a nested Dijkstra algorithm may solve your problem also in case of directed graphs.
I assume you are familiar with the Dijkstra algorithm, so I shorten the explanation to the essential:  


*

*create the $n\times n$ distance table and set its diagonal elements to $0$ and the off-diagonal elements to $+\infty$   

*create for every vertex $v_i$ a priority queue $q_i$ just as in the ordinary Dijksta algorithm and push $v_i$ into $q_i$  

*create a second "meta" priority queue $Q$ and push all $q_i$ into it; $Q$ is ordered according to the length of the shortest path from $v_i$ to $q_i$'s top element.  

*while $Q$ isn't empty, perform a "Dijkstra step" (i.e. popping of the top element and possibly relaxing the shortest path length from its root to the popped element) for $Q$'s top element, if that is w.l.o.g $q_i$, then $q_i$'s top element (w.l.o.g. $v_j$) is popped and possibly the length of the shortest path from $v_i$ to that element is relaxed (i.e. distance $d_{ij}$ is updated).
If $q_i$ isn't empty and if the distance of the new top element is less or equal the threshold value (30 in your example), reinsert it into $Q$  
That algorithm will report the routes in ascending order of length and only those whose length doesn't exceed the threshold value.  
If you are only interested in the routes and do not care about the order in which they are reported, you can do without $Q$ and start a Dijkstra route calculation for each node separately; each of those calculations can then be stopped if the top element's distance exceeds the threshold.
Using Fibonacci heaps as priority queues the runtime is $O(n(n\log(n)+m))$ where $n$ is the number of vertices and $m$ the number of edges.  
A: maybe this paper, in which the calculation of the all pairs shortest paths in $O(n^2)$ with high probability is solved, meets your requirements.
Some preconditions about the distribution of edge lengths are made, which you could check against the properties of your problem instances.
