idkhandle's blog

By idkhandle, history, 4 years ago, In English

Hello community. I came across an interesting problem where we are trying to find a longest (max nodes covered) with min edge wts cost ( sum of edge wts along the path is minimum). You can find a detailed explanation of the problem here: https://stackoverflow.com/questions/18861817/find-path-with-minimum-cost-and-maximum-length-given-a-maximum-cost

In addition to the graphical representation given there, we can have a node 0 from which we can start (node 0 is connected to every other node with a given weight). We can start from node 0, traverse as many nodes as possible and come back to node 0. In addition, we can traverse node 0 as many times as possible ( but node 0 is not counted in the final length). Any idea how to do this? We need max nodes covered with min path cost and under the given max cost constraint. ( Graph is fully connected)

Constraints:

If N is the number of nodes in the graph, then

1 <= N <= 2000

Also, If C is the max allowable wts cost along the path, the constraints are:

C <= 1e9

Any help would be appreciated :)

  • Vote: I like it
  • -8
  • Vote: I do not like it

| Write comment?