🔒 shortest_path

[pine pier]

shortest_path

[sullen junco]

@pine pier

Python help channel opened

Remember to:

• Ask your Python question, not if you can ask or if there's an expert who can help.
• Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
• Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.

[gritty basin]

Paste your code, and add print statements so you can trace the behavior of your code.

[pine pier]

def shortest_path(edges, src, dst):
    graph = build_graph(edges)
    shortest_distance = float("inf")
    curr_distance = 0
    for node in graph:
        curr_distance += find_distance(graph, node, dst, set(), 0)
        print(curr_distance)
    if curr_distance < shortest_distance:
       curr_distance, shortest_distance = shortest_distance, curr_distance

def find_distance(graph, src, dst, visited, count):
    for neighbor in graph[src]:
        if neighbor not in visited:
            visited.add(neighbor)
            count = 1
            count += find_distance(graph, src, dst, visited, count)
    return count

def build_graph(edges):
    graph = {}

    for edge in edges:
        a,b = edge
        if a not in graph:
          graph[a] = []
        if b not in graph:
          graph[b] = []
        graph[a].append(b)
        graph[b].append(a)

    return graph

edges = [
  ['w', 'x'],
  ['x', 'y'],
  ['z', 'y'],
  ['z', 'v'],
  ['w', 'v']
]

shortest_path(edges, 'w', 'z') # -> 2

[gritty basin]

Trying to debug without print statements is like trying to land an airplane with your eyes closed

[pine pier]

def shortest_path(edges, src, dst):
    graph = build_graph(edges)
    shortest_distance = float("inf")
    curr_distance = 0
    for node in graph:
        curr_distance += find_distance(graph, node, dst, set(), 0)
        print(curr_distance)
    if curr_distance < shortest_distance:
       curr_distance, shortest_distance = shortest_distance, curr_distance

def find_distance(graph, src, dst, visited, count):
    for neighbor in graph[src]:
        if neighbor not in visited:
            visited.add(neighbor)
            count = 1
            count += find_distance(graph, src, dst, visited, count)
    print(count)
    return count

def build_graph(edges):
    graph = {}

    for edge in edges:
        a,b = edge
        if a not in graph:
          graph[a] = []
        if b not in graph:
          graph[b] = []
        graph[a].append(b)
        graph[b].append(a)

    return graph

edges = [
  ['w', 'x'],
  ['x', 'y'],
  ['z', 'y'],
  ['z', 'v'],
  ['w', 'v']
]

shortest_path(edges, 'w', 'z') # -> 2

1
2
3
3
1
2
3
6
1
2
3
9
1
2
3
12
1
2
3
15

[gritty basin]

Add prints to see the neighbors and edges

[pine pier]

{'w': ['x', 'v'], 'x': ['w', 'y'], 'y': ['x', 'z'], 'z': ['y', 'v'], 'v': ['z', 'w']}

[gritty basin]

Take your code, and add print statements so that you see how the edges and count change for each iteration.

I'm just trying to help you solve this by adding information; if you see what happens on each iteration, you'll see why it keeps going to 15

[pine pier]

ok

[merry temple]

better to use a log...

[gritty basin]

For debugging a simple function, let's keep it simple 😉 print first, logging later

[pine pier]

how to know where to keep prints at such big program?

[gritty basin]

Whereever you modify the edges, for sure

[pine pier]

edegs never modified.

graph is constant across all calls

[gritty basin]

Visited: print changes to visited

[pine pier]

{'x'}
{'x', 'w'}
{'x', 'v', 'w'}
{'y', 'x', 'v', 'w'}
{'v'}
{'w', 'v'}
{'x', 'w', 'v'}
{'y', 'x', 'w', 'v'}

[gritty basin]

Ok, and what happens to count at each step?

WhT I'm trying to get you to do is, for each iteration/depth, print the state changes so you can see the root issue in find_distance. What I would do is: everytime find distance is called, print the parameters that are passed to it

[sullen junco]

Python help channel closed

This help channel has been closed and it's no longer possible to send messages here. If your question wasn't answered, feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.