Hi,

First, I'm programming in C. I'm not a real good programmer, and I have
a route problem. I have a robot that has to find the shortest route
through a maze. Options for doing this are either the A* or Dijkstra's
algorithm. My maze consists of 15 nodes, with each node only connected
to at least 1 of it's direct neighbours. All distances between the nodes
are the same. Since wikipedia tells me that A* is faster than Dijkstra,
I would like to know how the weights work out for either a linked list
or an array?

I hope my question is clear enough.

Thank you,

Huub

Since all the weights are the same, you can use breadth first search.
It's simpler (a queue instead of a priority queue) and faster (although
it won't make a difference for 15 node mazes).

Huub wrote:
You have automatically excluded all replies from those not familiar
with A* (whatever that may be) and/or Dijkstra's (who was a
remarkably able programmer and probably published thousands of
algorithms during his lifetime). You could have described the
algorithms or, if that is too long, given clear references to such
descriptions. I suspect your problems revolve around how to
represent a node.

--
Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

as possible. If I delete replies about algorithms, it's either
unintentional or I think (correctly or not) it's not really relevant.
And yes, I'm trying to figure out how to represent a node or an entire
graph. BTW, by the answers from all of you I'm trying to figure out
whether to use A*, Dijkstra or breadth-first. I thougt I had figured it
out, but now I'm in doubt again. In any case I want the simplest
algorithm for a 15 nodes graph.

Thank you.

In article <42DBBF17.821AEF7C@yahoo.com>, cbfalconer@yahoo.com says...
There's nothing wrong with the OP's question. There is only
one algorithm of Dijkstra's known as "Dijkstra's algorithm"
and it is taught in many computer science programs. See:

http://en.wikipedia.org/wiki/Dijkstra's_algorithm

The A* algorithm is taught in just about every introductory
AI class in the world:

http://en.wikipedia.org/wiki/A-star_algorithm


I don't see how you think that anyone unfamiliar with either
or both algorithms would be able to meaningfully comment on the
merits of the one algorithm over the other.


--
Christer Ericson
http://realtimecollisiondetection.net/

Christer Ericson wrote:
Well, on casual examination of my books here, I immediately find
Dijkstras algorithm as an extension to N processes of Dekkers
algorithm for mutual exclusion. I can also find his solution to
the Dining Philosophers problem.

I never took an introductory AI class, and I gravely doubt that I
ever will. Since the original problem (IIRC, you snipped any
evidence of it) showed similarities to traveling salesmen, I
suspect it requires some sort of exhaustive search. I have never
been noted for inability to comment, however I must leave the
'meaningful' adjective for others to apply.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson