4
\$\begingroup\$

I came across this problem while giving a sample test.

The problem was that we have given a tree which is undirected. We can start from any node of our choice. Initially we have power "P" and while going from one node to other node we loose some power "X" (consider as cost of travelling) and earn some profit "Y". So we need to tell that what is the maximum profit that we can earn with a given power ? Every node can be visited only once.

Example: First line contains number of nodes and initial power

Next n-1 lines contains node-node-cost-profit

5 4

1 2 1 2

1 3 2 3

1 4 2 4

4 5 2 2

Answer => 7. We can start from 4 and go to 1 and than to 3.

I have applied DFS on this to get maximum profit earned by traversing every single path.

But is there a way to decrease time ??? Can we apply floyd warshall algorithm to calculate distances each edges ??

from collections import defaultdict
class tree:
    def __init__(self,nodes):
        self.nodes = nodes
        self.graph = defaultdict(list)
    def add(self,a,b,charge,profit):
        self.graph[a].append([b,charge,profit])
        self.graph[b].append([a,charge,profit])
    def start(self,power):
        maxi = -1
        visited = [False for i in range(self.nodes)]
        for i in range(1,self.nodes+1):
            powers = power
            visited[i-1] = True
            for j in self.graph[i]:
                temp = self.dfs(j,powers,0,visited)
                if temp > maxi:
                    maxi = temp
            visited[i-1] = False
       return maxi

    def dfs(self,node,powers,profit,visited):
        v,p,pro=node[0],node[1],node[2]
        if powers-p < 0:
            return 0
        if powers-p == 0:
            return profit + pro
        profit += pro
        powers = powers-p
        visited[v-1] = True
        tempo = profit
        for k in self.graph[v]:
            if visited[k[0]-1] == False:
                temp = self.dfs(k,powers,tempo,visited)
                if temp > profit:
                    profit = temp
        visited[v-1] = False
        return profit

t = tree(5)
t.add(1,2,1,2)
t.add(1,3,2,3)
t.add(1,4,2,4)
t.add(4,5,2,2)
print(t.start(4))
\$\endgroup\$
  • 1
    \$\begingroup\$ Is it allowed to visit a node more than once? The code assumes that it is not, but the problem description does not say one way or the other. Can you edit the question to make this clear? \$\endgroup\$ – Gareth Rees Aug 22 at 10:38
  • \$\begingroup\$ A node can be visited once . Yes, I will modify the question. \$\endgroup\$ – learner-coder Aug 23 at 2:17
2
\$\begingroup\$

Firstly, use a PEP8 checker. It will raise a lot of issues about whitespace and also tell you to change

            if visited[k[0]-1] == False:

to either

            if visited[k[0]-1] is False:

or

            if not visited[k[0]-1]:

The DFS is far more complicated than necessary:

  • We don't need visited: given that we know that the graph is a tree, it suffices to track the previous vertex.
  • I'm used to DFS tracking vertices, not edges.
  • There's no reason for dfs to take profit as an argument: the profit that can be made in a rooted subtree is independent of the profit made getting there.

Rewriting with those notes in mind, we can reduce it to

    def start(self, power):
        return max(self.dfs(u, power, None) for u in range(1, self.nodes+1))

    def dfs(self, u, power, prev):
        return max((edge[2] + self.dfs(edge[0], power - edge[1], u)
                    for edge in self.graph[u]
                    if edge[0] != prev and edge[1] <= power),
                   default=0)

However, I think this is still inefficient in some cases. It's doing \$n\$ depth-first searches, for overall time \$\Theta(n^2)\$. But those searches are traversing the same vertices. I believe (although I haven't written the code to verify it) that it should be possible to do it in \$\Theta(np)\$ where \$p\$ is the starting power. The idea would be to do one DFS, but for each subtree to return a complicated structure containing the largest score available solely within that subtree, and the largest scores available from the root of that subtree for different powers (which would obviously be monotonically increasing). Then it would be necessary to combine these.

(Floyd-Warshall is cubic time, so that would be worse. Similarly, matrix-based all-pairs-shortest-path algorithms for general graphs would be worse).

\$\endgroup\$

Your Answer

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

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