curriculum/challenges/english/blocks/learn-algorithm-design-by-building-a-shortest-path-algorithm/6557913b8fe5c0bc834c9f4f.md
The .extend() method, allows you to add elements from an iterable to the end of a list:
my_list = ['larch', 'birch']
tree_list = ['fir', 'redwood', 'pine']
my_list.extend(tree_list)
print(my_list) # Output: ['larch', 'birch', 'fir', 'redwood', 'pine']
Create an else clause and use the .extend() method to add the current node path to the neighbor node path.
You should create an else clause after your nested if statement.
({ test: () => {
const commentless_code = __helpers.python.removeComments(code);
const {block_body} = __helpers.python.getBlock(commentless_code, /if\s+distance\s*\+\s*distances\s*\[\s*current\s*\]\s*<\s*distances\s*\[\s*node\s*\]\s*/);
assert(block_body.match(/^\s+else\s*:/m));
}
})
You should have paths[node].extend(paths[current]) in your else clause.
({ test: () => {
const shortest = __helpers.python.getDef(code, "shortest_path");
const {function_body} = shortest;
assert(function_body.match(/^(\s*)if\s+paths\s*\[\s*node\s*\]\s*\[\s*-\s*1\s*\]\s*==\s*node\s*:\s*^\1(\s{4})paths\s*\[\s*node\s*\]\s*=\s*paths\s*\[\s*current\s*\]\s*^\1else\s*:\s*^\1\2paths\s*\[\s*node\s*\]\s*\.extend\s*\(\s*paths\s*\[\s*current\s*\]\s*\)/ms));
}
})
my_graph = {
'A': [('B', 3), ('D', 1)],
'B': [('A', 3), ('C', 4)],
'C': [('B', 4), ('D', 7)],
'D': [('A', 1), ('C', 7)]
}
def shortest_path(graph, start):
unvisited = list(graph)
distances = {node: 0 if node == start else float('inf') for node in graph}
paths = {node: [] for node in graph}
paths[start].append(start)
while unvisited:
current = min(unvisited, key=distances.get)
for node, distance in graph[current]:
if distance + distances[current] < distances[node]:
distances[node] = distance + distances[current]
--fcc-editable-region--
if paths[node][-1] == node:
paths[node] = paths[current]
--fcc-editable-region--
print(f'Unvisited: {unvisited}\nDistances: {distances}\nPaths: {paths}')
#shortest_path(my_graph, 'A')