Say in a map i need to find the shortest path between two cities A and B. If i run a single source shortest path algorithm to solve it , it will find the shortest path from vertex A to the all the other cities in the World. So it will take a long time to come up with an answer. So then single path shortest path algorithms are not suitable to find shortest path when the no of vertices in the graph is very large such as in the above case
Are my arguments correct.
Please correct me if iam wrong.
Consider yourself corrected.
Your argument fails to use common sense - you would never consider going to NY via South Africa, so why should your program?
With more nodes/routes to consider, there will be more analysis needed to find the shortest path, but good logic finds the way, in short order.
So can you use Dijkstra's algorithm to find shortest path between two cities in a world map?
Sure. That's probably what it's used the most for, routing.
Dijkstra's algorithm - Wikipedia, the free encyclopedia
Let's say you're going to UK from, say, Sweden, and the planes only leave every 48 hours, and hours to US leaves every hour.
Now, from the US, planes leave for UK every hour.
So in some cases, it might be faster to go US -> UK than Sweden -> UK directly.
And to detect thing, the algorithm needs to examine every node.
It might not be the least expensive alternative, but it's certainly the shortest (if you count in terms of hours). And that's what the algorithm is all about.
Last edited by Elysia; 07-10-2010 at 08:28 AM.
Originally Posted by Adak
Okay now say i have a world map containing x number of cities and i want to find the shortest path between cities A and B in country A. Now if i were to run the algorithm all the time the user selects two cities it will not be practical as there are a huge no of cities , it would take a long time to give the result. So how do i really overcome this problem?
Do i have to run the shortest path algorithm on all the combinations and save the result in a table so the next time the user selects two cities the table value is retrieved instead of recalculating?
You can certainly save the calculated path if you've done it once so long as there is no dynamic elements involved (for example, what if roadblocks appear on ways?).
Otherwise you have to populate the graph with the relevant items and then run the algorithm.
Please dig a hole, and bury this "it will not be practical" idea. Put rocks on top of the gravesite, so you can't dig it back up, again.
Dijikstra was a brilliant computer scientist, and this algorithm is quite fast. Obviously, if you need to keep this information around for subsequent route selection, do that, rather than recalculating it.
Instead of talking ABOUT it, why not use the pseudo code that Wikipedia has on the site I linked to earlier, and write up your own version, and then you can TEST it, using actual figures. You'll be able to see and test it's run time, on your particular problem.
I have a working Dijkstra algorithm, actually, for those who are too lazy to write one (it can be somewhat difficult).
Not to say it's performance is top-notch, but I don't suppose it's a slouch either.
