Matlab graph theory asymptotic complexity

Question

I've recently become interested in graph theory and after investing with the bioinformatics toolbox for MATLAB I have found the graphshortestpath function incredibly useful. However, when using the function the run times are always very similar, whether I set the function to Breadth-first search, Dijkstra's algorithm or Bellman Ford algorithm. I have tried with varying amounts of nodes from a few hundred to hundreds of thousands and still the run times are almost identical.

Now on the graphshortestpath page on the MATLAB website Dijkstra's algorithm shows a time complexity that would suggest it would be substantially faster than the other two algorithms.

From what I have read the time complexity is more of a worst case scenario, but I was expecting to see at least a slight difference in run times.

see here (http://www.mathworks.co.uk/help/bioinfo/ref/graphshortestpath.html)

Am I missing something here?

Any help would be greatly appreciated.

Answer 1

Just a guess here, but depending on how you are measuring the performance, you might be spending a lot of time actually drawing the graph path -- which is likely to cost more than the actual search.

Try adding timing metrics that exclude the drawing process before compare. Note of course, that your dependency will be not only on the number of vertices, but also, the number of edges in your graph.