实现Dijkstra算法时Graph类意外修改外部init_graph的问题

问题现象 #

实现Dijkstra算法时编写图结构代码，出现异常：类内构造的graph局部变量与外部传入的init_graph打印结果完全一致，不符合预期。

代码实现 #

class Graph(object):
    def __init__(self, nodes, init_graph):
        self.nodes = nodes
        self.graph = self.construct_graph(nodes, init_graph)
    def construct_graph(self, nodes, init_graph):
        '''
        This method makes sure that the graph is symmetrical.
        In other words, if there's a path from node A to B with a value V, there needs to be a path from node B to node A with a value V.
        :param self:
        :param nodes:
        :param init_graph:
        :return:
        '''
        graph = {}
        for node in nodes:
            graph[node] = {}
        graph.update(init_graph)
        for node, edges in graph.items():
            for adjacent_node, value in edges.items():
                if graph[adjacent_node].get(node, False) == False:
                    graph[adjacent_node][node] = value
        print(graph)
        return graph

if __name__=="__main__":
    nodes = ["Reykjavik", "Oslo", "Moscow", "London", "Rome", "Berlin", "Belgrade", "Athens"]
    init_graph = {}
    for node in nodes:
        init_graph[node] = {}
    init_graph["Reykjavik"]["Oslo"] = 5
    init_graph["Reykjavik"]["London"] = 4
    init_graph["Oslo"]["Berlin"] = 1
    init_graph["Oslo"]["Moscow"] = 3
    init_graph["Moscow"]["Belgrade"] = 5
    init_graph["Moscow"]["Athens"] = 4
    init_graph["Athens"]["Belgrade"] = 1
    init_graph["Rome"]["Berlin"] = 2
    init_graph["Rome"]["Athens"] = 2

    graph = Graph(nodes, init_graph)

    print(init_graph)

实际输出 #

{'Reykjavik': {'Oslo': 5, 'London': 4}, 'Oslo': {'Berlin': 1, 'Moscow': 3, 'Reykjavik': 5}, 'Moscow': {'Belgrade': 5, 'Athens': 4, 'Oslo': 3}, 'London': {'Reykjavik': 4}, 'Rome': {'Berlin': 2, 'Athens': 2}, 'Berlin': {'Oslo': 1, 'Rome': 2}, 'Belgrade': {'Moscow': 5, 'Athens': 1}, 'Athens': {'Belgrade': 1, 'Moscow': 4, 'Rome': 2}}
{'Reykjavik': {'Oslo': 5, 'London': 4}, 'Oslo': {'Berlin': 1, 'Moscow': 3, 'Reykjavik': 5}, 'Moscow': {'Belgrade': 5, 'Athens': 4, 'Oslo': 3}, 'London': {'Reykjavik': 4}, 'Rome': {'Berlin': 2, 'Athens': 2}, 'Berlin': {'Oslo': 1, 'Rome': 2}, 'Belgrade': {'Moscow': 5, 'Athens': 1}, 'Athens': {'Belgrade': 1, 'Moscow': 4, 'Rome': 2}}

预期输出 #

{'Reykjavik': {'Oslo': 5, 'London': 4}, 'Oslo': {'Berlin': 1, 'Moscow': 3, 'Reykjavik': 5}, 'Moscow': {'Belgrade': 5, 'Athens': 4, 'Oslo': 3}, 'London': {'Reykjavik': 4}, 'Rome': {'Berlin': 2, 'Athens': 2}, 'Berlin': {'Oslo': 1, 'Rome': 2}, 'Belgrade': {'Moscow': 5, 'Athens': 1}, 'Athens': {'Belgrade': 1, 'Moscow': 4, 'Rome': 2}}
{'Reykjavik': {'Oslo': 5, 'London': 4}, 'Oslo': {'Berlin': 1, 'Moscow': 3}, 'Moscow': {'Belgrade': 5, 'Athens': 4}, 'London': {}, 'Rome': {'Berlin': 2, 'Athens': 2}, 'Berlin': {}, 'Belgrade': {}, 'Athens': {'Belgrade': 1}}

问题原因 #

Python中字典是可变对象，graph.update(init_graph)执行时，只是将init_graph中每个节点对应的边字典的引用复制到了graph中，而非创建独立的副本。后续补全对称边时，直接修改了这些共享的边字典，导致外部的init_graph也被同步修改。

解决方案 #

修改construct_graph方法，为每个节点的边字典创建独立副本，避免引用共享：

class Graph(object):
    def __init__(self, nodes, init_graph):
        self.nodes = nodes
        self.graph = self.construct_graph(nodes, init_graph)
    def construct_graph(self, nodes, init_graph):
        '''
        This method makes sure that the graph is symmetrical.
        In other words, if there's a path from node A to B with a value V, there needs to be a path from node B to node A with a value V.
        :param self:
        :param nodes:
        :param init_graph:
        :return:
        '''
        graph = {}
        for node in nodes:
            # 为每个节点的边字典创建副本，避免引用共享
            graph[node] = init_graph[node].copy()
        for node, edges in graph.items():
            for adjacent_node, value in edges.items():
                if graph[adjacent_node].get(node, False) == False:
                    graph[adjacent_node][node] = value
        print(graph)
        return graph

if __name__=="__main__":
    nodes = ["Reykjavik", "Oslo", "Moscow", "London", "Rome", "Berlin", "Belgrade", "Athens"]
    init_graph = {}
    for node in nodes:
        init_graph[node] = {}
    init_graph["Reykjavik"]["Oslo"] = 5
    init_graph["Reykjavik"]["London"] = 4
    init_graph["Oslo"]["Berlin"] = 1
    init_graph["Oslo"]["Moscow"] = 3
    init_graph["Moscow"]["Belgrade"] = 5
    init_graph["Moscow"]["Athens"] = 4
    init_graph["Athens"]["Belgrade"] = 1
    init_graph["Rome"]["Berlin"] = 2
    init_graph["Rome"]["Athens"] = 2

    graph = Graph(nodes, init_graph)

    print(init_graph)

修改后，graph中的边字典是独立副本，补全对称边的操作不会影响外部的init_graph，即可得到预期输出。

内容的提问来源于stack exchange，提问作者Milon Sarker