Maximum profit earned on weighted un-directed tree 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 &gt; 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 &lt; 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 &gt; 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))
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] &lt;= 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).