I'm trying to implement Dijkstra alogorthim. While doing so, I've coded graph part. I'm observing this strange output. Not sure which feature causing this. I'm getting same output for two print though one is local variable and another is in class.

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)

Output :

{'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}}

Expected Output :

{'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}}

CodePudding user response：

graph.update(init_graph) creates references to the nested dictionaries in init_graph rather than creating a separate copy. This allows the data in init_graph to be overwritten and is causing the strange outputs.

This fixed the issue for me:

from copy import deepcopy

graph = Graph(nodes, deepcopy(init_graph))

Here's some info on dictionary copying that was helpful for me: Copy a Python Dictionary: A Complete Guide