CODEWITHSUNDEEP
graphpath-finding
root
root

Reputation: 1583

Pathfinding algorithm

Given a directed graph, starting point, ending point and a time limit. At each vertices, there's a "value" that represents how much attractive this location is. There's also a cost of traveling from vertices to another.

What i need is to find a path that is within the time limit and has the maximum "value".

Upvotes: 2

Views: 437

Answers (1)

Codor
Codor

Reputation: 17605

To answer the question in part, note that the considered problem is NP-hard as it contains the Knapsack problem as a subproblem using the following reduction.

Given an instance of the Knapsack problem given by n items defined by profits p_1,...,p_n and weights w_1,...,w_n and a target capacity C, define a graph as follows.

To the left there is a source node s and a terminal node t to the right. For the i-th item define two nodes yes_i and no_i, which correspond to selecting and not selecting the respective item. The attractiveness of the yes-nodes is p_i and the attractiveness of the no-nodes is zero.

The pairs of nodes can be imagined as arranged in columns between the source and the terminal. Each node has in two in-edges from the previous column (except for the first colum, which is connected to the source). The weight of each of these edges is w_i if and only if they are the in-edges of a yes-node and zero if they are in-edges of a no-node. The last column is connected to the terminal.

Each path from s to t must column-wise decide whether or not to select the item of the respective colum; likewise, any selection of items corresponds to a path from s to t. By definition of the edge weights, the total weight of the path is equal to the total weight of the selection of items, while the total weight of the selected yes-nodes is equal to the the total weight of the selected items.

In total, we obtain a bijection of the feasible solutions of the Knapsack instance and the constructed instance of the described path problem. In total, this means that the problem in the question is NP-hard as it contains the Knapsack problem (which is known to be NP-hard) as a subproblem.

Alternatively the NP-hardness can be seen by setting the attractiveness of all locations in a complete graph to one; this special case of the problem is the decision version of the Hamiltonian Path problem, which is known to be NP-complete.

Upvotes: 1

Related Questions