CODEWITHSUNDEEP
javaalgorithmgraph-theory
Gal
Gal

Reputation: 381

find a cyclic path with a certain node with a certain weight

I am trying to build a navigation app. Im trying to think of an algorithm to find a cyclic path that includes a certain node and sums up to a certain weight. the input for the algorithm would be a node and a weight.

Example: algo(a,30) - the algorithm wil return a path that can start from node A and finish in Node A and the total sum of it is 30.

extra info: for all w:weights w>0, the graph is directional (as streets are).

thanks ahead Gal

Upvotes: 0

Views: 208

Answers (2)

amit
amit

Reputation: 178471

The general problem is NP-Hard, and reduceable from the longest path problem, and thus is NP-Hard, and there is no known polynomial solution to this problem (and the general assumption is such a solution does not exist).

The longest path problem is: Given a graph G with weight function w, and a pair of vertices u,v - find the longest path from u to v.

Proof:
Assuming there is a polynomial algorithm to your problem - one can build an algorithm to longest path problem, with binary search (exponentially increase the wanted weight, until there is no solution, and then - binary search). Each step is polynomial, and there are O(log|PATH|) steps. Since log|PATH| is polynomial in the input (assuming simple pathes), the algorithm is polynomial.

It is also closely related to Hamiltonian Path Problem and Traveling Salesman Problem

Upvotes: 1

lavin
lavin

Reputation: 2416

This problem is stronger ( more difficult) than the Hamiltonian Cycle Problem. Because if we already have a solution for this problem algo(a,b), for any Hamiltonian Cycle Problem P we can design a new graph with weight=1 for edges in P and 0 for edges not, then use algo(1,n) to find a Hamiltonian Cycle, in which n is number of nodes in the graph. So we have a NP-complete problem here.

For applications with small n, a brute-force search with certain "pruning" should work fast enough.

Upvotes: 1

Related Questions