Hi,

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

In article <42db816d$0$782$3a628fcd@reader20.nntp.hccnet.nl>, Huub
<hdotvdotniekerkathccnetdotnl> says...
A* is faster than Dijkstra only when the overhead of the more
complicated calculation is balanced out by the usefulness of the
distance heuristic.

For 15 nodes, both should take about a microsecond, so it doesn't
matter which you use.

By 'weights', I can only assume you mean the length of each route. In
you case you can take this as unity since all distances are the same.

- Gerry Quinn

Huub <hdotvdotniekerkathccnetdotnl> wrote:

He means 1, the integer value that lies between 0 and 2.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
mail: rjh at above domain

either A* or Dijkstra, all distance-weights are 1 and the way to
implement either algorithm is by using priority queues.
But if all distances are the same, then what does it select the priority on?

Huub <hdotvdotniekerkathccnetdotnl> wrote:


The priority is a combination of the cost of entering the node and the
estimated distance to the goal node from the current node.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
mail: rjh at above domain