I fail to see how this is different than Dijkstra''s algorithm on a non-directed graph, exchanging the source & destination nodes...
In fact, since you''re unclear about whether you update nodes multiple times(once everytime they are encountered) i have to assume that you do so(correctness would force you to do so), and since you make no mention of how this is done, i assume a brute force solution...which is ass slow. So in fact either your algorithm is wrong, or it''s a slow implementation of Dijkstra''s...

I was actually pointing out that precomputing each node could take up a lot of memory depending on how many nodes each node can link to.

quote: Original post by bpj1138
You only have to compute the distance variables once, whenever you change your destination node.

Not if you discover a shorter way through a node while you''re computing other distances.
For instance, in this trivial case, imagine 3 nodes, a,b and c.
a->b costs 1
b->c costs 1
a->c costs 3

Let''s say you wanna get from a to c.
Now, you go through your algorithm...first pass, start at c.
What can get to c? a and b.
so, you check a to b
a->b + b->c = 1 + infinity
then, check a to c
a->c + c->c = 3 + 0
After checking all edges out of a, you conclude that the fastest way to get from a to c(so far) is 3.

Now your algorithm would actually terminate, which would be incorrect, but even supposing it didn''t.
update b
check b to a
b->a + a->c = 1 + 3 = 4
check b to c
b->c + c->c = 1 + 0 = 1
So now you know the fastest way to get from b to c.
But, you have to update node a to use this new piece of information.
a->b + b->c = 1 + 1 = 2, a new fastest route
Therefore you must update nodes multiple times.

Additionally, this can be computed on the fly(for changing edge costs/blocked edges, occupied nodes, etc) and be thread safe if each thread has its own copy of the "cheapest path so far" list...which would have to be copied anyway, since you wouldn''t want to compute the same path in 2 threads at once.

quote: Original post by bpj1138
I think it's hilarious the responses I get about this algorithm..

1) does it even work?
2) it must be A*
3) trivial
4) depth first search (that was a new one)
5) __________ (what will it be next?)

If you wish to be condescending to others in this forum, I suggest you take it elsewhere.

quote: Original post by bpj1138
I don't think people even know what A* is. A* is not even an algorithm. Not a complete one, anyway. It just says that instead of doing a full recursive search, you can use various huristics to narrow the search, A* doesn't define the huristic.

You might also want to verify for yourself that A* is indeed an algorithm. In fact, it's not just an algorithm, but given certain constraints on the search problem, its also an optimally efficient algorithm (certainly optimally efficient relative to any other algorithm given the same constraints), which means that it will find the solution path (if it exists) and do so by searching fewer nodes than any other algorithm.

As to my earlier statement about your search being DFS, I did state that I may have been mis-reading your post. However, upon reflection it still appears that your algorithm implements a variation on the depth first theme where the 'variation' is a version of uniform cost search. Your costs though are heuristics based on the node-goal distance, rather than the usual start-node distance used in uniform cost pathfinding algorithms.

This is why your algorithm looks like Dijkstra's with the start and goal nodes reversed (because Dijkstra's is an optimal solution for uniform cost search of a graph structure).

If you'd like to justify your algorithm as being better, or more efficient than some other algorithm, then you should offer up its computational complexity and an estimate of the time complexity to search a graph of n nodes. This would at least give us a basis of comparison to other known algorithms so that we might assess the benefits of your algorithm.

Timkin

Edited by - Timkin on September 14, 2001 4:34:58 AM

you missed the point...
I wasn''t (just) pointing out an ommision in your code.
Rather, I''m trying to get you to understand, that through ignorance or intention, you posted a (very slightly) modified version of Dijkstra''s algorithm, with a naive implementation.

If you actually discovered this yourself, my congratulations. Perhaps the most important lesson to be learned here is that you don''t always have to reinvent the wheel...a little bit of research can go a long way, especially when claiming ownership for an idea.

However, you have still left many issues untouched. Do you know what the cost of your recursion is? Very likely, it is prohibitive, and the implementation is not straightforward. Do you know when to terminate this recursion? What''s the base case?

Is there a better way you could compute the cheapest cost?(HINT - use some sort of data structure)

p.s. If you want a challenge, try to compute the second-most shortest path - that is, the shortest path not counting the shortest =P

quote: Original post by bpj1138
Which brings me to another point, you said my implmentation is "naive". I take that as a compliment, because I strive to make my code as simple as possible, even if it sacrifices some efficiency. Code clarity is number one concern.

I think what is meant here, is that since the algorithm is already well-known and published, the ''clarity'' is not in question. Therefore the existing challenge is in efficient implementations of the algorithm rather than clean ones, which can often be a close mirror of the algorithm''s pseudocode. Admittedly, a clean-but-slow implementation can be a decent starting point and a learning tool.