Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a problem which I've reduced down to the following requirements:

Given an:

  • undirected graph $G$ that may contain cycles, with positive weighted nodes and edges of length $1$,
  • a subset of nodes $M$,
  • a length $L$,

return the path of maximum weight (calculated by summing up the weights of its nodes) that contains all nodes in $M$ and is exactly length $L$.

(A more complex requirement that I'm omitting is that including certain nodes in the path may increase the values of other nodes.)

I'm just looking for a nod in the right direction - are there any algorithms or terms that might be relevant to this situation?

share|cite|improve this question
If $L+1$ happens to be the number of nodes in the graph and the path is required to be simple, this becomes the Hamiltonian path problem... – Rahul Jan 27 '13 at 1:00

Could be something like "Weight Constrained Shortest Path" or "Restricted Shortest Path"

share|cite|improve this answer
Googling these terms returns a number of links. Even though links can go stale, some references or links would add to this answer. – robjohn Feb 4 '13 at 16:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.