Google Answers Logo
View Question
Q: Dijkstra's Algorithm run over all USA roads- Runtime needed. ( No Answer,   3 Comments )
Subject: Dijkstra's Algorithm run over all USA roads- Runtime needed.
Category: Computers > Algorithms
Asked by: shaynethebrain-ga
List Price: $2.38
Posted: 29 Sep 2005 15:00 PDT
Expires: 29 Oct 2005 15:00 PDT
Question ID: 574387
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."


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.
There is no answer at this time.

Subject: Re: Dijkstra's Algorithm run over all USA roads- Runtime needed.
From: nejla-ga on 26 Oct 2005 14:00 PDT
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
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.
Subject: Re: Dijkstra's Algorithm run over all USA roads- Runtime needed.
From: nejla-ga on 28 Oct 2005 02:27 PDT
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
Subject: Re: Dijkstra's Algorithm run over all USA roads- Runtime needed.
From: pacostacos-ga on 04 Nov 2005 10:32 PST
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.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  

Google Home - Answers FAQ - Terms of Service - Privacy Policy