Given is an undirected weighted graph with N nodes, with each node having a property/Value.

Aim is to find the bestpath which maximizes the sum of the nodes property which can be visited given a constraint on the maximum distance/weight than can be traversed over the entire graph i.e. the sum of edge weights of best path found should not exceed the the constraint specified on the weight. The best path should begin and end at the same node.

I am trying to solve the above as a knapsack problem while using Djikstras,seems too complex to put in code. Would appreciate some help with alternate methods if my thinking is wrong.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.