View Question
Q: Dijkstra's Algorithm run over all USA roads- Runtime needed. ( No Answer,   3 Comments )
 Question
 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." 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.```
 Answer
 There is no answer at this time.

 Comments
 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 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```
 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 Nejla```
 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 answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for

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