shortest path algorithm

Printable View

April 22nd, 2008, 09:51 PM
idyll09

shortest path algorithm

i going to develop an application for finding the shortest path.my application will read a coordinate from a text file(which had been extract from a static map).
i'm intend to apply dijkstra and A* algorithm for my application.i do made a prog(but not using the dijkstra and A* algorithm) so it will calc the shortest path,but it produced nothing.seems it read infinity...

my question..
1)how i'm gonna to know that my program work well by selecting right node so that it reach the final destination where all the weight=1?
in other words,as dijkstra used least accumulated cost to reach its final destination,how i want to know that my program select the next-lowest cost since the weight for each vertex=1?

2)as i'm googled in internet,all i found that the dijkstra and A* most used in graph and games.it is the same if i apply it for my application?if not,how do i modified it so it can be apply to my app.

i'm really hope for some comments/opinion/ thought/help...

thanks!
April 22nd, 2008, 10:07 PM
dglienna

Re: shortest path algorithm

Here you go!

http://www.codeproject.com/KB/recipe...lculation.aspx
April 26th, 2008, 09:06 AM
idyll09

Re: shortest path algorithm

sory for late reply..

tq dglienna..i already take look at that link..

but now i encounter another problem regarding shortest path problem..

there are 4 category of shortest path problem.my prob is regarding single destination shortest path problem.
the single destination shortest path problem is equivalent to single source shortest problem.but all direction reversed.

can i still used dijkstra algorithm in solving this problem?
or is there any other algorithm which is more suitable that this one?

need some help..i'm really appreciate it..!
tq!
April 27th, 2008, 02:47 PM
prometheuzz

Re: shortest path algorithm

Quote:

Originally Posted by idyll09

...

the single destination shortest path problem is equivalent to single source shortest problem.but all direction reversed.

can i still used dijkstra algorithm in solving this problem?
or is there any other algorithm which is more suitable that this one?

Yes, as long as the weights of the edges in your graph are non-negative, Dijkstra will do just fine for the single-source shortest-path and/or the single-destination shortest-path problem.