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

[lmoh3479]

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

freeCodeCamp.org

[pkdvalis]

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

[lmoh3479]

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

[pkdvalis]

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.

[lmoh3479]

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

[pkdvalis]

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?

[edi.sugi1996]

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

[pkdvalis]

Good catch about the search