Sounds like you're trying to solve a variation of weighted undirected hamiltonian path problem (which is NP-complete).
One good "exact" straightforward solution that I know of for your problem uses O(N*2^N) memory and O(N^2*2^N) running time (can be easily optimized by the order of N), which is by running the Dijkstra algorithm and defining a Node as pair of (current location, bitvector of all visited nodes) and destination node as (<any location>, bitvector where all nodes have been visited). You can also try the "approximate" solution with some heuristic search instead, which runs in significantly less time and less memory. -Kurniady On Mon, Nov 22, 2010 at 7:37 PM, Sakthi Priyan <[email protected]> wrote: > I am sorry. I didn't explain my problem clearly at first shot. > It goes like this > Assume there are five nodes in a graph. I am giving the Adjacency Matrix > here. > 1 2 3 4 5 > 1 0 1 1 1 1 > 2 1 0 1 0 0 > 3 1 1 0 0 0 > 4 1 0 0 0 1 > 5 1 0 0 1 0 > Now I need to visit all the nodes with minimum weights crossed. This is the > problem :( > Here we have two closely connected components (CCC), 123 and 145. And node 1 > acts like a bridge between those CCC. If I enter any of those CCC, I need to > touch node 1 again to reach the other. So, if I mark node 1 as visited at > first, the program will start from 1 and lets say it touches 2 and then it > ll touch 3. From 3, it has to go to 1 and by that time node 1 is marked as > visited. So program 'll halt there and 'll give wrong result. > Please suggest... > > On Mon, Nov 22, 2010 at 9:52 AM, vineel yalamarth > <[email protected]> wrote: >> >> >> Try using a visited flag for all the nodes. Initialise it to zero and >> toggle it when you traverse through it,.Based on status of visited flag, you >> can avoid visiting the visited nodes. >> >> Regards, >> Vineel. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "google-codejam" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/google-code?hl=en. > > > > -- > - Thanks and Regards, > > Sakthipriyan > > -- > You received this message because you are subscribed to the Google Groups > "google-codejam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/google-code?hl=en. > -- You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
