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
I was reading about Graphs. Almost all texts, are solving problems with
acyclic graphs only. So I just wanted to try cyclic graph.
Carlos,
As you said, its really difficult to come up with a generic solution it
seems... But still me and my friend Shyam is working on this. We are just
discussing a
>
> 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.
This part, for that exam
On Mon, Nov 22, 2010 at 9:37 AM, Sakthi Priyan
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
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.
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
Hi all,
Is there a way to traverse a weighted cyclic directed graph?
I tried BFS and DFS. They both fail when there is a closed loop in the
graph.
- Thanks and Regards,
*Sakthipriyan*
--
You received this message because you are subscribed to the Google Groups
"google-codejam" group.
To post
