ologn_13's blog

Visiting all nodes in a weighted directed graph with shortest path length
By ologn_13, 12 years ago, In English

Hi all! I was solving this problem:- We are given a weighted directed graph. We have to find the route with minimum length and it should visit all the nodes with a node not visited more than once. Please help in tackling it!! Thanks for reading it.

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, can you please provide the problem link if available? I'm interested about the constraints of the number of nodes, edges etc.

Thanks

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Actually, there is still no polynomial algorithm for this problem. The only way to solve it is using backtracking.

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is a "cyclic graph"? This term is rarely used in programming tasks, so maybe you meant acyclic graph?

→ Reply