I am following a blog related to 'shortest path' algorithms in python, and the code works well. However, there is a single line in the code that has me confused, and I hope that you can help explain it to me.

In the code below, I would like to understand what this line is doing?

new_path = current_path[:]

Why do I get a different result when I change this line to

new_path = current_path

Here is the entire code:

# Construct the graph
graph = {'0':{'.','1','2'},
         '.':{'0','3'},
         '1':{'0','2','4'},
         '2':{'0','1','3','5'},
         '3':{'.','2'},
         '4':{'1','5','7'},         
         '5':{'2','4','6','8'},
         '6':{'3','5','9'},         
         '7':{'4','8'},
         '8':{'5','7','9'},         
         '9':{'6','8'}}


# Function to return the shortest path between two nodes in a graph
def shortest_path(graph, start_node, end_node):
    path_list = [[start_node]]
    path_index = 0
    
    # To keep track of previously visited nodes
    previous_nodes = {start_node}
    if start_node == end_node:
        return path_list[0]
        
    while path_index < len(path_list):
        current_path = path_list[path_index]
        last_node = current_path[-1]
        next_nodes = graph[last_node]
        
        # Search for the end node within the list of next_nodes
        if end_node in next_nodes:
            current_path.append(end_node)
            return current_path
        
        # Add new paths
        for next_node in next_nodes:
            if not next_node in previous_nodes:
                new_path = current_path[:]        # <-----------------------This line
                new_path.append(next_node)
                path_list.append(new_path)
                
                # To avoid backtracking
                previous_nodes.add(next_node)
                
        # Continue to next path in list
        path_index  = 1
    
    # No path is found
    return []


# Print the shortest path from 1 to 9 in the graph
print(shortest_path(graph, '1','9'))    

CodePudding user response：

It kinda copies the list!

The colon syntax means slicing (you can read about this here). In your example it evaluates to current_path[0:len(current_path)] so it's the slice that covers all list.

The difference is simple

l1 = [1]
l2 = l1 # here you assign the reference, so l2 and l1 points to the same list!
l2.append(2)
print(l1) # [1, 2]
l3 = l1[:] # now it's a new reference
l3.append(3)
print(l1) # [1, 2]