Thread: exhaustive graph search

My program reads vertices and edges in from a file and creates a graph. I need to create an exhaustive search that finds the shortest path (determined by weight) to visit all vertices starting with a designated vertex.
A simple visual representation of the graph may look something like:

Code:

          4
%      G-----H
%      |    /|
%      |  1/ |
%     8|  /  |8 
%      | /   |      
%      |/    |        
%      A-----C
          4

(The numbers are the weight of the edge)
So, i would need to find the shortest path to visit all vertices starting with vertex G (the vertices are actually identified by their id. I used letters so they wouldn't be confused with the weights).
I'm not sure how to do this. I know it is similar to a depth-first search. I was thinking about doing a depth-first search to visit all the vertices. Then, go one vertex back and call the depth first search again, and keep doing this until i'm back to the beginning.
My program works with the depth-first search, so i just need to figure out how to do the exhaustive search, i'm just not sure how to go about it.

Any help would be greatly appreciated.
Thanks

Btw, i think this is called the traveling sales person problem (or something like that)



here is my depth-first search if needed:

Code:

int DepthSearch()
{
	cout << endl;
	cout << "Depth-first Search:" << endl;
	cout << endl;

	vertex *currentVertex;

	//Set all vertices color to white (not discovered)
	for(unsigned int i = 0; i < vertexArray.size(); i++)
	{
		if(vertexArray[i] != NULL)
		{
			vertexArray[i]->color = "white";
		}
	}

	int time = 0;

	for(unsigned int i = 0; i < vertexArray.size(); i++)
	{
		if(vertexArray[i] != NULL)
		{
			if(vertexArray[i]->color == "white")
			{
				currentVertex = vertexArray[i];
				DepthSearchVisit(currentVertex, time);
			}
		}
	}

	return 0;
}
int DepthSearchVisit(vertex *currentVertex, int &time)
{
	edge *adjEdge;
	adjEdge = currentVertex->next;

	currentVertex->color = "gray";
	cout << "Discovered Vertex: " << " Id: " << setw(2) << left << currentVertex->id << "  Label: " << currentVertex->label << endl;

	time = time + 1;
	currentVertex->discovTime = time;

	while(adjEdge != NULL)
	{
		if(vertexArray[adjEdge->target]->color == "white")
		{			
			DepthSearchVisit(vertexArray[adjEdge->target], time);
			cout << setw(10) << left << "Visited" << " Vertex: " << " Id: " << setw(2) << currentVertex->id << "  Label: " << currentVertex->label << endl;
		}
		adjEdge = adjEdge->nextEdge;
	}

	currentVertex->color = "black";
	cout << setw(10) << left << "Finished" << " Vertex: " << " Id: " << setw(2) << currentVertex->id << "  Label: " << currentVertex->label << endl;
	time = time + 1;
	currentVertex->finished = time;

	return 0;
}