Path Finding Using Adjacency List.

Background: Im not trying to impliment any particular algorithm, but id like to do a little pathfinding. Im storing several things in several places while testing different ideas. Each node object has a list of adjacencies (std::list<Node*>), and the Network object has a list of all nodes, and a map of lists of adjacencies sorted by node name (std::map<std::string, std::list<Node*> >).

My question: How do i go about taking the current stored information and go about finding paths from one node to another? Right now im simply interested in shortest path implimentations. Im interested in real code here, not abstract imagery. If i wanted that id read a book.

The current working (although not SHORTEST path) function im using is something like this:

Code:

---

Node* NodeNetwork::FindBestNextHopBetween(Node* Current, Node* Destination, int depth)
{
        if(depth>NetworkNodes.size()) { return NULL; }//failure due to routing loop.
        std::list<Node*>::iterator AdjacenciesIter;
        for(AdjacenciesIter=Current->Adjacencies.begin();AdjacenciesIter!=Current->Adjacencies.end();AdjacenciesIter++)
        {
                if((*AdjacenciesIter)==Destination)
                {
                        return Current;
                }
                Node* NextBestHopTemp = FindBestNextHopBetween((*AdjacenciesIter), Destination, depth+1);
                if(NextBestHopTemp==(*AdjacenciesIter))
                {
                        if(depth==0) {return NextBestHopTemp; } //we are at the top, return our next found hop.
                        if(depth!=0) {
                                return Current; //we are deep, go up a level.
                        }
                }
        }
        return NULL;//failure
}

---

Anyways, any imput you could offer would be a great help. Eventually id like to impliment a possible weighting system for adjacencies, however im saving the complicated stuff for another day =P.

Edit: After a little testing, i believe my code always takes the longest path lol. it will even bounce back and forth until it finds a path exactly as long as the node list. Thats to be expected i suppose. The problem i have with "shortest path" is that to find the shortest path, i have to find all the paths and then pick the shortest one. Seems kinda wasteful of resources. Oh well, ill get it eventually. =P

Hum.. you need Dijkstra's algorithm for graphs shortest path.
http://ciips.ee.uwa.edu.au/~morris/Y.../dijkstra.html
This link has what you need. The algorithm is very simple. Click the "Run animation" button in the bottom for a Java applet animation. It's very clear what happens.
In your case, just asume that every link has cost 1.

I've already done a Java application with a very cool GUI that calculates shortest paths between node in graphs. I could upload it if you want :P

Im afraid i dont know java, and have had alot of trouble in the past extrapolating information from applications writen in it. There are arbitrary objects, like Graph. What is a graph? how is it stored and accessed. Id like to do this with the current datastructures I have if possible.

Thanks for your help, ill try and watch the animation when my browser decides to let java work. Maybe that will pound into my head the solution.

you don't need to know java.. just have the java vm installed on your computer
Get it herre http://java.sun.com/j2se/1.5.0/download.jsp
Choose Downlaod JRE 5.0 Update 3
Second.. a graph is just a data structure, which matches perfectly to what you're doing
Nodes connected to each other. Each node has a collection of links to other nodes...
Look at the animation, each ball is a node. At the end you have the shortest path.

I watched the animation, and im more confused than ever. This is why i need code and not theory. Id really like to see code in a language i knew without the use of a bunch of structures that are in librarys i dont know about.

No.. you definetly need theory... You're not going to draft around chuncks of code waiting that something comes up (expontaneous generation)... with theory, the algorithm is easily built

Different people learn in different ways. Some people read books to learn how to build bridges, others build bridges to learn how to build bridges.

I learn far better looking at working code and then derive the theory behind it, and if i make alot of mistakes through trial and error trying to write my own, all the better.

trivial stuff works that way...

Here it goes: your objective it to go from node A to Z through the shortest path (smaller number of visited nodes). Dijkstra algorithm has a small extra - there can be a cost from a node P to Q which can be anything, and the point is to find the path with lower cost.
Because you want to store the path, each node will have a collection (stl vector will do) of nodes which represents the path taken from the origin to that node. Also each node must have a variable to store the cost of reaching it. In your case, all connections have cost 1.

First you need to setup up the cost of all nodes. For the first set it to 0, for all others set them to infinite (INT_MAX, FLOAT_MAX, or a number greater than the number of nodes).

Second you need to have 2 globals vars for the algorithm to work, which should be 2 set's, to ease up a bit. The first set stores the non-visited nodes, which costs must be calculated. The second set stores the already visited nodes, with no need for calculations.

Now the algorithm works like this:
Select the node with lower cost from the not-visited ones. We'll call it A. Foreach adjacent node X, consider the cost it has stored. If the cost from X is lower or equal than the cost from A+1, do nothing. Else set the cost of X to A+1, and set the path it stores to the path of A + node X.
Then all nodes X are removed from the visited node's set, and placed in the not-visited node's set, which means that their adjacent nodes have to be also recalculated. And place node A
in the visited node's one. Note that if you're working with a set it'll automaticly discard inserting of a already present node.

In something like peseudo-code it'll be like:

Code:

---

list<Node*> all_nodes;
list<Node*>::iterator lni;

int infinity = INT_MAX;//something

for(lni = all_nodes.begin();lni<all_nodes.end();lni++)
        (*lni)->cost = infinity;

all_nodes[initial_node_index]->cost = 0;

set<Node*> notvis = all_nodes;
set<Node*> vis;

while(notvis.size()>0){//while there are nodes to process
        Node *n = find_min_node(notvis);//get the node with lower cost

        for(lni = n->Adjacencies.begin();lni<n->Adjacencies.end();lni++){
                if( (*lni)->cost > n->cost+1){
                        //set new cost
                        (*lni)->cost = n->cost+1;

                        //set new path
                        (*lni)->path = n->path;
                        (*lni)->path.insert(*lni);

                        vis.remove(*lni);
                        notvis.insert(*lni);
                }
        }
        notvis.remove(n);
        vis.insert(n);       
}

---