Skip to content

Instantly share code, notes, and snippets.

@tugloo1
Created April 3, 2018 22:24
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save tugloo1/a017f0fcffe0a67cfae5e3ec2d85cf21 to your computer and use it in GitHub Desktop.
Save tugloo1/a017f0fcffe0a67cfae5e3ec2d85cf21 to your computer and use it in GitHub Desktop.
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