Learn Algorithm Design by Building a Shortest Path Algorithm - Step 50

Python
1

Tell us what’s happening:

I cannot progress through the exercise, even though I can’t see what’s wrong with my code.

I’ve checked forum answers, and it seems this module was updated recently so I can’t find instruction that match my current step. Checked indentation, but it’s unchanged from the previous step so it cannot be a source of error. The exercise propmt asks us to check if paths[node] exists before we check the content of its last element – I’m doing so by checking if paths[node] is Truthy, and combining it with the previous condition that was already there.

The hint we get is " You should add paths[node] as the first condition to your nested if statement. Use the and operator to combine your conditions.". I literally added paths[node as the first condition to my if and used an and operator to combine the conditions, and yet, nothing.

Literally, I believe I’ve done what the prompt asks me to do and I still cannot pass. The hints are not really helping me further, nor are past forum posts. I don’t love coming to the forum with what I believe to be a very simple/basic question, but I’m completely stuck and out of ideas of what could be going wrong at this point, making me question the test instead of my code.

Anyway, enough ranting. I’m a bit frustrated because this exercise, while teaching valuable skills, is very hard to follow. The concept of a shortest path through graphs makes sense to me, but doing that only with text (no images) and with several new data structures has been a bit overwhelming.

Thanks!

Your code so far

my_graph = {
    'A': [('B', 3), ('D', 1)],
    'B': [('A', 3), ('C', 4)],
    'C': [('B', 4), ('D', 7)],
    'D': [('A', 1), ('C', 7)]
}

def shortest_path(graph, start):
    unvisited = list(graph)
    distances = {node: 0 if node == start else float('inf') for node in graph}
    paths = {node: [] for node in graph}
    paths[start].append(start)
    
    while unvisited:
        current = min(unvisited, key=distances.get)
        for node, distance in graph[current]:
            if distance + distances[current] < distances[node]:
                distances[node] = distance + distances[current]

# User Editable Region

                if paths[node] and paths[node][-1]:
                    paths[node] = paths[current]

# User Editable Region

                else:
                    paths[node].extend(paths[current])
                paths[node].append(node)
        unvisited.remove(current)
    
    print(f'Unvisited: {unvisited}\nDistances: {distances}\nPaths: {paths}')
    
#shortest_path(my_graph, 'A')

Your browser information:

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:133.0) Gecko/20100101 Firefox/133.0

Challenge Information:

Learn Algorithm Design by Building a Shortest Path Algorithm - Step 50

2

initially the if was if paths[node][-1] == node:
you removed a piece when adding the new condition

1 Like
3

That seems to be the case - I originally played with a few other conditions, and even thou I Ctrl+Z multiple times, I probably didn’t Ctrl+Z enough times to go back to the original condition.

A good reminder for myself to always reset the lesson instead of relying on Ctrl+Z in these cases.

Thank you very much and apologies again for the small rant earlier. I appreciate it