Learn Algorithm Design by Building a Shortest Path Algorithm - Step 47

Tell us what’s happening:

I don’t understand this error at all: You should use the slice syntax to assign a copy of `paths[current]` to the neighbor node path.

That’s what I did? Neither the instructions nor the feedback provide assistance on how to improve.

Thoughts?

``````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]

/* User Editable Region */

if paths[node] and paths[node][-1] == node:
paths[current] = paths[node]

/* User Editable Region */

paths[node].extend(paths[current])
paths[node].append(node)
unvisited.remove(current)

print(f'Unvisited: {unvisited}\nDistances: {distances}\nPaths: {paths}')

shortest_path(my_graph, 'A')

``````

User Agent is: `Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/120.0.0.0 Safari/537.36`

Challenge Information:

Learn Algorithm Design by Building a Shortest Path Algorithm - Step 47

I’ve linked to just the part about slicing, but the beginning of the article describes why this is important

I tried a lot of the ideas present in the link but I still get the same error. (The output looks fine though, which is why I’m even more confused.)

There is only 1 method you need to try, slice: `my_duplicate_list = my_list[:]`

You are copying the list, by creating a new list, by using a slice of the list from beginning to end. You just need to add `[:]` to the end of `paths[current]`

``````paths[node] = paths[current]
my_duplicate_list = my_list
``````

This is a normal assignment, but the problem is that these still point to the same list in memory. To make a real copy, create a new list by making a full slice:

``````my_duplicate_list = my_list[:]
``````

This creates a new list and not just a new pointer.

2 Likes

Thank you so much- this question was so confusing and your clear explanation really sorted it out.

I’m not familiar with this new content yet, and it’s still in beta, so there might be areas to improve.

Did this build off a previous lesson involving copying lists using slicing?

There was slicing in previous project within the lesson, however the current project does not clearly explain the need to slice.

Step 47 Instructions

The other bug is subtle. When a shorter distance is found for a neighbor node, `paths[current]` gets assigned to the neighbor node path, `paths[node]`.

This means both variables point to the same list. Since lists are mutable, when you append the neighbor node to its path, both `paths[node]` and `paths[current]` are modified because they are the same list. This results in wrong paths, although the distances are correct.

Fix that bug by assigning a copy of `paths[current]` to the neighbor node path. Modify the existing assignment inside your `if` block.

``````# This was default
if paths[node] and paths[node][-1] == node:
paths[node] = paths[current]

# However, this code does not pass
if paths[node] and paths[node][-1] == node:
paths[node] = paths[current].copy()
``````

Error Instructions:

Sorry, your code does not pass. Keep trying.

You should use the slice syntax to assign a copy of `paths[current]` to the neighbor node path.

My Takeaway:

—> Yes , the error instruction is to slice whole list. However, it was never been explained before that this will make a copy when we are building a project about list manipulation

→ Also, I have just noticed that the search for help prompt will never display any answered result.

This is because it is redirected to:
https://forum.freecodecamp.org/search?q=learn-algorithm-design-by-building-a-shortest-path-algorithm%20-%20Step%2047

While it should’ve been redirected to:
https://forum.freecodecamp.org/search?q=Learn%20Algorithm%20Design%20by%20Building%20a%20Shortest%20Path%20Algorithm%20-%20Step%2047

1 Like