

Subject:
Dijkstra's Algorithm run over all USA roads Runtime needed.
Category: Computers > Algorithms Asked by: shaynethebrainga List Price: $2.38 
Posted:
29 Sep 2005 15:00 PDT
Expires: 29 Oct 2005 15:00 PDT Question ID: 574387 

There is no answer at this time. 

Subject:
Re: Dijkstra's Algorithm run over all USA roads Runtime needed.
From: nejlaga 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 BigO 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 BigO 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: nejlaga on 28 Oct 2005 02:27 PDT 
Dear Friend, My input were not dimwitted. 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 metaheuristic 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: pacostacosga 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. 
If you feel that you have found inappropriate content, please let us know by emailing us at answerssupport@google.com with the question ID listed above. Thank you. 
Search Google Answers for 
Google Home  Answers FAQ  Terms of Service  Privacy Policy 