How long would it take to run Dijkstra's algorithm on the entire US,
or North American road system? Use any underlying representation you
wish, but you must include at a minimum: the Big-O runtime, the
runtime in seconds on a "typical PC", and the approximate number of
vertices and edges.

An example answer should look something like: "According to _________,
it would take _____ years to run Dijkstra's algorithm, using a
Fibonacci Heap, which is O(V*logV + E), on a Pentium 4 3Ghz PC, for
all _______ roads and _______ intersections within the contiguous
United States of America."

Thanks!

---

Clarification of Question by shaynethebrain-ga on 27 Oct 2005 11:45 PDT

Thank you for your comment.
I have found a "formula" for my problem on my own, so I do not need
this solution anymore.
Thanks for your input, however dim-witted it may be.

The Dijkstra algorithm finds the shortest path from one node of a
graph to other nodes of the graph in a Greedy fashion. The Big-O of
the algorithm is N^2 where N is the number of nodes in the graph. In
your problem Nodes are US citis and Edges are roads which conect these
cities. The Big-O of the algorithm doesn't depend on E (Number of
edges).
But you can't ask axactly how many seconds it will take on a pc.
Because the exact time depends on lots of factors. The CPU speed is
just one of them. It So I suppose it is imposible to give a formula
for the exact time of your question. You should get your answers by
just simulation.
Nejla

Dear Friend,
My input were not dim-witted. Again I say what you want has no
formula. Did you consider something like memory access time, number of
threads, Sequential or Parallel processing, the architecture of your
system, ...?!
Just to give you a background I must say, I am working on QoS
Multicast routing with meta-heuristic techniques like genetic
algorithms and tabu search for more than 1 year. In this case I read
all papers and books (more than 1000 pages) in this matter and I am
familiar with lots of dynamicprogramming, greedy, heuristic and
artificial life techniques for finding shortest paths, minimum
spanning tree, Minimum Steiner Tree and also the constrained ones like
Floyd, Prim, Kruskal, Dijkstra, Kth shortest path, KMP, KPP, BSMA, RS,
TM, KMB, Breadth Depth Search,.... In all papers till I read (all
IEEE, ACM, Elsevier), no one gave a formula like what you said and
they all evaluate the performance of their proposed algorithms with
just simulations.
So I suppose your formula is not a correct one. But if you think I
suggest you to publish it as a novel approach in the way of evaluating
the performance of algorithms. That will help researchers alot! But
remember you should demonstrate its accuracy
all the best
Nejla

Dijkstra's runs O(n^2)?!  Mabye if this is your first implementation. 
Anyway, shaynethebrain has a valid question that I am supprised no one
answered, since all the google researchers do is google the
information lol.  It seems to be he is allowing any form of processing
as long as it is described, see his "example answer".  Also note the
"according to ____", it's pretty obvious the person who answers this
question would only be refrencing someone else who had already ran a
simulation or used a formula to estimate the time needed.

PS: Nejla, your name dropping attempt is laughable.