Created
April 3, 2018 22:24
-
-
Save tugloo1/a017f0fcffe0a67cfae5e3ec2d85cf21 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def calculate_path_weight(node, seen_nodes, current_weight): | |
# Case when we've seen all the nodes | |
if set(seen_nodes) == set(input_graph.keys()): | |
return current_weight | |
to_return_path_weight = 10000 | |
for path_node, path_weight in input_graph[node]: | |
if path_node not in seen_nodes: | |
new_seen_nodes = seen_nodes + [path_node] | |
total_path_weight = calculate_path_weight(path_node, new_seen_nodes, current_weight + path_weight) | |
if total_path_weight < to_return_path_weight: | |
to_return_path_weight = total_path_weight | |
return to_return_path_weight | |
input_graph = {'A': [('B', 2)], 'B': [('A', 2), ('C', 5)], 'C': [('B', 5)]} | |
starting_node = 'A' | |
print(calculate_path_weight(starting_node, [starting_node], 0)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment