CODEWITHSUNDEEP
algorithmgraphpath
Robert Toth
Robert Toth

Reputation: 91

Optimal Graph path containing n nodes

Is there an established algorithm for finding a path from point A to point B in a directed-weighted graph which visits exactly N nodes, but not necessarily any nodes in particular?

Upvotes: 1

Views: 485

Answers (3)

Wei
Wei

Reputation: 738

I am not sure if I undersand it correctly, can you do a depth first search (up to N-1 layers away from the source)?

If you can visit your destination in that layer. you can get a path down there.

Upvotes: 0

templatetypedef
templatetypedef

Reputation: 373482

This problem is known to be NP-hard via a reduction from Hamiltonian path. In particular, you can solve Hamiltonian path with a polynomial-time reduction to this problem as follows: for each possible pair of nodes (s, t) in a graph with n nodes, ask if there is a path from s to t that passes through exactly n nodes. This makes only polynomial calls to your solver, so any polynomial-time solution to your problem would result in a polynomial-time solution to the Hamiltonian path problem.

So in short, you shouldn't expect a polynomial-time algorithm for this problem unless P = NP.

Upvotes: 4

dfb
dfb

Reputation: 13289

I'm going to assume you're trying to find the shortest/longest weight with N nodes. This probably isn't optimal, but from your original graph, you could generate a state graph with 'N*(#Nodes)' nodes representing consisting of the original node and number of steps taken and run it thorough some shortest path algorithm like http://en.wikipedia.org/wiki/Dijkstra's_algorithm.

i.e.,

A->B->C
 \___/

becomes 

(A,0)->(B,1)->(C,2)
  \>(C,1)

Your target node would then be node (B,N) - B with N steps. This approach would allow for loops in the original graph if it's not a DAG ( (X,0)->(Y,1)->(X,2) )

Upvotes: 0

Related Questions