Joe - 1 year ago 186

Python Question

I'm trying to find each node distance from the starting node and the connections between the nodes is given in a dictionary

My code works well with small dictionary like this example but the problem with dictionaries with more than 20 nodes I got an error

`if child != parent and child not in my_list:`

RecursionError: maximum recursion depth exceeded in comparison

I'm stuck here, can anyone help me?

My code

`def compute_distance(node, dic, node_distance, count, parent, my_list):`

children = dic[node]

node_distance[node].append(count)

for child in children:

if child != parent and child not in my_list:

compute_distance(child, dic, node_distance, count + 1, node, children)

node_distance_dic = {}

node_distance_dic = {k: min(v) for k, v in node_distance.items()}

return node_distance_dic

if __name__ == '__main__':

starting_node = 9

dic = {0: [1, 3], 1: [0, 3, 4], 2: [3, 5],

3: [0, 1, 2, 4, 5, 6], 4: [1, 3, 6, 7],

5: [2, 3, 6], 6: [3, 4, 5, 7, 8],

7: [4, 6, 8, 9], 8: [6, 7, 9], 9: [7, 8]}

print(compute_distance(starting_node, dic, defaultdict(list), 0, 0, []))

Output(key = node, value = distance)

`{0: 4, 1: 3, 2: 4, 3: 3, 4: 2, 5: 3, 6: 2, 7: 1, 8: 1, 9: 0}`

Answer

I guess `my_list`

is here to keep track of the nodes already visited, but you never update it. Therefore, you should add the node you are processing in order not to call recursion on nodes that you already went through. Currently, your code goes in infinite loop as soon as there is a cycle in the graph. Plus, don't forget to pass it to the next level:

```
def compute_distance(node, dic, node_distance, count, parent, my_list):
my_list.append(node)
...
compute_distance(child, dic, node_distance, count + 1, node, my_list)
...
```

However, this method does not compute the shortest path from the starting node to every other, it just do a simple traversal of the graph (underlying algorithm is DFS).

In order to implement what you want, that is the min distance from the source to every other node, you should look into Breadth-First Search (commonly called BFS).

It will solve your problem in linear time.

Source (Stackoverflow)