Hi, I have five nodes, all connected in all ways possible, and I want to search the sortest path between tow of this nodes, selected randomly, I am going to use the A* algorithm, but there are things that I don''t understand, one is how the nodes are stored in the priority queue and list, its a queue of list of nodes? I explain me: queue (letters are nodes): position 0: A-B-C-D position 1: A-C-D position 2: A-C-D-E .... I know how to do a queue of ints for example, but I don''t know how it can be done a queue of a list of nodes (paths).

A priority queue is a completely different data structure than a queue. Priority queues are actually more like trees, and usually their computational complexity resembles trees more than queues, but they are highly specialized to be more efficient than trees at what they do.

And what do they do? You add items to the priority queue, and the each item is associated with a key. All the keys are ordered in some way (usually the keys can just be integers or floats). The priority queue has a remove item operation that will find the item with the lowest key value, return it, and remove it from the queue. Usually priority queues are implemented as some sort of heap, although a tree could also work, it would just have a little extra overhead. A slightly more advanced implementation could implement a reduce key operation to allow keys to be efficiently changed after they have already been inserted into the priority queue.

In network searches, a priority queue is used to choose which node to expand next. Each node, when it is added to the open list, has a cost associated with it. In A*, this cost is the cost to reach the node plus the estimate of how far the node is from the goal (the heuristic). The node to expand next is the one with the lowest cost. This is exactly what a priority queue does, so it is a highly efficient way to implement A*. The reduce key operation might also be necessary, in case a better path is found to a node already on the open list (to implement the reduce key operation, the priority queue can also have a hash table to look up the items that are stored in it and find their position in the heap).

For many purposes, a priority queue isn''t even necessary, and you can get results just as good by simply using a list of nodes and keeping the list sorted by inserting nodes in sorted order. This doesn''t scale as well as a priority queue, but for small problems it can work just as well or better because their is less overhead.

A* doesn''t actually store complete paths. Each node just keeps track of which node it was reached from. When the goal is found, the goal node has the node that it was reached from, that node has its parent, all the way back to the starting node, so the path from the end to the start can be found.

Maybe try doing something simpler first, like a uniform cost search. Actually, you might have to just use a uniform cost search anyway, since you just seem to have a random network with no underlying pattern and no way to generate a heuristic.