Thread: 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