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

Tell us what’s happening:

Describe your issue in detail here.
Trying to add an additional condition to the nested if statement to ensure that paths[node] is non-empty before accessing paths[node][-1] .

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]
            if paths[node] != [] and paths[node][-1] == node:
                paths[node] = paths[current]
            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’)

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] == node:
                    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) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/121.0.0.0 Safari/537.36

Challenge Information:

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

You appear to have created this post without editing the template. Please edit your post to Tell us what’s happening in your own words.

The code seems correct to me, but here the test requires you to do it in a different way. You should use the truthiness of the value, meaning that the first condition should be the list itself. You don’t need to compare it with anything.

Hi, please open a new topic for this question, thanks!

If you have a question about a specific challenge as it relates to your written code for that challenge and need some help, click the Ask for Help button located on the challenge (it looks like a question mark). This button only appears if you have tried to submit an answer at least three times.

The Ask for Help button will create a new topic with all code you have written and include a link to the challenge also. You will still be able to ask any questions in the post before submitting it to the forum.

Thank you.

Instead of using “paths[node] != ”,
Use --removed—

It is great that you solved the challenge, but instead of posting your full working solution, it is best to stay focused on answering the original poster’s question(s) and help guide them with hints and suggestions to solve their own issues with the challenge.

We are trying to cut back on the number of spoiler solutions found on the forum and instead focus on helping other campers with their questions and definitely not posting full working solutions.

1 Like