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?

Your code so far

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')

Your browser information:

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

Read about copying lists using slice here:
https://therenegadecoder.com/code/how-to-clone-a-list-in-python/#copy-a-list-using-a-slice

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.)

Can you please share your updated code?

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

Good catch about the search :+1: