Difference between creating a new list an mutating an existing one

Question

I'm trying to calculate the shortest path from a node start to another end in a graph. I've been reading that the + operator, applied to a list, concatenates an element to the end of the former, creating a new list as a result. Whereas using .extend() not only does the same of adding the elements to the end of the list but also keeps the same list instance.

I can't see why if I use path = path + [start] my code works, and not if I use path.extend(start). I don't see the need of creating a new list each time the function is called for it to return the right results.

def shortest_path_edge_num(graph, start, end, path = None, shortest = None):
    if (graph or start or end) is None: return None
    if path is None: path = []
    if shortest is None: 
        shortest = []

    path = path + [start]
    # path.extend([start])
    # Base case:
    if start == end: return path

    for adj_node in graph[start]:
        if adj_node[0] not in path:
        new_path = shortest_path_edge_num(graph, adj_node[0], end, path, shortest)
            if new_path:
                if (not shortest) or (len(new_path) < len(shortest)):
                    shortest = new_path
    return shortest

# Main routine
graph = {
    'A' : [('B',5),('F',10)],
    'B' : [('A',5),('E',2),('C',4)],
    'C' : [('B',4),('D',11)],
    'D' : [('C',11),('E',7)],
    'E' : [('B',2),('D',7),('F',1)],
    'F' : [('A',10),('E',1)]
}

print shortest_path_edge_num(graph,'A','C')

>>> python graph.py
['A', 'B', 'C']
>>> # But when changing to path.extend([start])
>>> python graph.py
['A', 'B', 'E', 'D', 'C', 'F']

EDIT

Using + creates a new instance of list, thus all the other variables that depend in some way of it don't change each time I add a new element to path. Now the question should be how should I remove that dependence?

Answer 1

path.extend() is expecting another sequence as its argument. The same as you said path + [start], you need to say path.extend([start]). The easier way, however, would be to use .append(): path.append(start). Here are the docs on list.

Answer 2

I wasn't aware that applying operations to path will result in modifications in other variables such as new_pathor shortest. When I saw that doing path.append(start) or path.extend([start]) also added start to the other two lists I realized that I should not use path when calling the function recursively in new_path = shortest_path_edge_num(graph, adj_node[0], end, path, shortest) but instead use path[:] so as to send a copy of the list and not the reference.

So in the end I kept the line path.append(start) or path.extend([start]) and modified the parameter path[:] in the recursive call. By doing that the program returned the shortest path as expected.

Thanks for the comments and the answers.