An answer to this question on Stack Overflow.

Question

I'm working on a C++ program where we must traverse a graph of vertices and weighted edges in a way that we start at a user-specified vertex and then end at the same vertex after a certain desired distance has been traveled. I am not sure how to implement this with code, but I have this so far:

void DijkstrasShortestPath()
{
	while (vertices.size() != 0)
	{
		Vertex* u = extract_min(vertices);
		vector<Vertex*>* adjVertex = AdjVertices(u);
		const int size = adjVertex->size();
		for (int i=0; i<size; ++i)
		{
			Vertex* v = adjVertex->at(i);
			int distance = travel_dist(u, v) +
				u->distFromStart;
			
			if (distance < v->distFromStart)
			{
				v->distFromStart = distance;
				v->previous = u;
			}
		}
		delete adjVertex;
	}
}
Vertex* extract_min(vector<Vertex*>& vertices)
{
	int size = vertices.size();
	if (size == 0) {
		return NULL;
	}
	int minimum = 0;
	Vertex* min = vertices.at(0);
	int i = 0;
	for( i=1; i<size; ++i)
	{
		Vertex* temp = vertices.at(i);
		if( temp->distFromStart < min->distFromStart) {
			min = temp;
			minimum = i;
		}
	}
	vertices.erase(vertices.begin() + minimum);
	return min;
}
vector <Vertex*>* AdjVertices(Vertex* vert)
{
	vector<Vertex*>* adjVertex = new vector <Vertex*> ();
	const int size = edges.size();
	for(int i=0; i<size; ++i)
	{
		Edge* edge = edges.at(i);
		Vertex* adjacent = NULL;
		if (edge->intersection1 == vert)
		{
			adjacent = edge->intersection2;
		}
		else if (edge->intersection2 == vert)
		{
			adjacent = edge->intersection1;
		}
		if (adjacent && vertices_check(vertices, adjacent))
		{
			adjVertex->push_back(adjacent);
		}
	}
	return adjVertex;
}
int travel_dist(Vertex* u, Vertex* v)
{
	const int size = edges.size();
	for(int i=0; i<size; ++i)
	{
		Edge* edge = edges.at(i);
		if (edge->street_connection(u, v))
		{
			return edge->distance;
		}
	}
	return -1;
}
bool vertices_check(vector<Vertex*>& vertices, Vertex* vert)
{
	const int size = vertices.size();
	for(int i=0; i<size; ++i)
	{
		if (vert == vertices.at(i))
		{
			return true;
		}
	}
	return false;
}

This is essentially the Dijkstra's Shortest Path algorithm, which is not exactly what I want. What I'm trying to do is get the program to calculate a route thats distance is within 1 unit of a user-specified distance and starts and ends at the same vertex. Is there any way I can do that by changing what I have?

Does this call for a Breadth-First Search or a Depth-First search instead of Dijkstra's Algorithm?

Answer

One possible method.

You could use a bounded best-first search.

Create a structure P which stores a list of nodes forming the potential loop, along with the length of the loop created so far.

Seed the search at the specified vertex S by making a separate P-structure for each of the nodes which S links to. Add these P-structures to a priority queue which is sorted by the length of the path described by the P-structure.

Consider each of these nodes in turn removing their P-structures from the priority queue, copying their P-structures, and appending the nodes they link to. If the node to be added is already present in the P-structure and not it is not S, then discard the structure and do not consider that route any longer. Similarly, if any path exceeds the specified cost C, then discard that path and do not consider it any longer. If the path has not been discarded, add its associated P-structure to the priority-queue.

If S does appear in a P-structure twice and the length of the path described by the P-structure is within the permitted range, then exit successfully. If not, continue the search until the priortiy-queue is empty.

You may be able speed up the algorithm by using an admissible heuristic to guesstimate the distance from a given node to S, adding this to the established cost of the path-in-progress, and using the sum as the sorting key for the priority queue. Such heuristics are at the heart of the A* algorithm, which may be of interest to you.

Is this clear? If not, I could writing a short example code.