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;
}

---

You have to visit all the vertices, correct? So you need to try all (n-1)! possible ways to order the n vertices. In your example, you need to check
GACHG
GAHCG
GCAHG
GCHAG
GHACG
GHCAG
(4-1)! = 6. There are permutation-generating algorithms out there to generate permutations; once you have a permutation, you just add up all the edges (or call it infinity if an edge is missing, like GCAHG where you just can't do G->C).

Quote:

---

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

---

Yes, the "traveling salesman" problem is where you need to visit every vertex using the shortest path possible. If that is indeed what you're trying to do, then you'll want to take a look at this:

Dijkstra's Algorithm

Hope it helps!

Isn't Dijkstra's Algorithm used for finding the shortest distance from the source vertex to a target vertex? In this problem there isn't a designated target, because it must visit all vertices, and a different target may result in a shorter distance.

Ok, i got the permutation method to work for a small number of vertices (like 1-10). However, the number of vertices of my graphs may be up to 25. I can't get my permutation algorithm to work on a graph with that many vertices, because there are too many possible permutations (it now seems that it is working, just taking a long time. For example, with N=12, it takes 3 minutes to run). Is there a way to solve this problem?


Here is the permutation algorithm i'm using. If i change N (the number of permutations) to a high number (like 20) it runs forever. Also, i couldn't figure out how to make it only generate permutations that begin with 1.

Code:

---

#include <iostream>
using namespace std;


void print(const int *v, const int size)
{       
        if (v != 0)
        {       
                for (int i = 0; i < size; i++)
                {                       
                        cout << v[i] << " ";
                }
                cout << endl;
        }
}
void visit(int *Value, int N, int k)
{       
        static int level = -1;
        level = level+1;
        Value[k] = level;
       
        if (level == N)
        {
                print(Value, N);
        }
        else
        {                       
                for (int i = 0; i < N; i++)
                {                       
                        if (Value[i] == 0)
                        {                               
                                visit(Value, N, i);                               
                        }
                }
        }
        level = level-1;
        Value[k] = 0;       
}
int main()
{
        const int N = 4;
        int Value[N] = {NULL};

        visit(Value, N, 0);       
       

        return 0;
}

---

Thanks.

*Edited

Quote:

---

Originally Posted by Cpro

Ok, i got the permutation method to work for a small number of vertices (like 1-10). However, the number of vertices of my graphs may be up to 25. I can't get my permutation algorithm to work on a graph with that many vertices, because there are too many possible permutations (it now seems that it is working, just taking a long time.

---

That's the point. There's a million dollars in it for you if you can find a way to solve it quickly.

Oh, and to get the permutations that start with 1, you print 1 before the loop, and generate a permutation on N-1 elements (and add 1 to the results from inside the permutation function). And of course you'll have to tack the 1 back onto the end too.