Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Find minimum path sum from root to leaf - using queue and find pruning idea
def get_cheapest_cost(rootNode):
if rootNode is None:
return None
queue = [(rootNode, rootNode.cost)] # []
min_found_cost = None # None
while len(queue) > 0:
curr_pair = queue.pop()
curr_node = curr_pair[0] # 1 node
curr_cost = curr_pair[1] # 7
if len(curr_node.children) == 0:
if curr_cost < min_found_cost:
min_found_cost = curr_cost
continue
for child in curr_node.children:
child_cost = child.cost + curr_cost
if min_found_cost is not None and child_cost >= min_found_cost:
continue
queue.insert(0, (child, child_cost))
return min_found_cost
##########################################
# Use the helper code below to implement #
# and test your function above #
##########################################
# A node
class Node:
# Constructor to create a new node
def __init__(self, cost):
self.cost = cost
self.children = []
self.parent = None
"""
make queue of (node, total cost)
add children of root
min_found_cost variable
while queue not empty
take current child off queue and add its children
add child's cost to parent's total cost
save cost alongside child node
if min_found_cost is not None and new cost >= min_found_cost, don't need to continue on this branch
return min_found_cost
"""
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.