Graph - Running time measurements of Dijkstra39s algorithm

Questions

http://en.wikipedia.org/wiki/Dijkstra http://en.wikipedia.org/wiki/Dijkstra

Now, the complexity for this implementation is according to Wikipedia: O((|V|+|E|) log |V|).

When I ran the algorithm on V = 1000, e.g. a graph with 1000 nodes (I dont know how many edges though), on average it took about 800 ms. When I doubled the size of the graph with V = 2000, it took around 1700 ms, and when I doubled that (V = 4000), it took about twice as much.

So my question is (I know that my computer plays some part in the time measurements as well), shouldn t the running times be faster? Are these measurements reasonable?

Answers

These measurements are reasonable; however, the runtime complexity is both worst-case and asymptotic. In fact, it would be most useful to evaluate the running times on instances where the worst-case is actually reached to experimentally estimate the runtime complexity.

Source

License : cc by-sa 3.0

http://stackoverflow.com/questions/25527403/running-time-measurements-of-dijkstras-algorithm

Related