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

Python
1

Tell us what’s happening:

Hello! I have tried multiple times to solve this problem, I put the paths[node] at the beginning of the if, but it didn’t work. I also tried the code I have right here (The editable region) and it also didn’t work. Can someone give me the answer and explain it a bit because I can’t seem to find it?

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

                paths[node][-1] == node if paths[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/122.0.0.0 Safari/537.36

Challenge Information:

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

2

Here is the hint I get if I test your code:

You should add paths[node] as the first condition to your nested if statement. Use the and operator to combine your conditions.

An example if statement with 2 conditions:

if a == 1 and b == 2:
    do this

if a and num == 2:
    do that

Hope this helps!

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

I still did not understand because I think I have tried what you said… The text above is what I typed now.

4

This is much better, you have the correct syntax :+1:

Two things:

You should add paths[node] as the first condition

a = 1
if a:
   do this

You can check if a value is true or false like this. If a is 0, it will be false, but if it’s > 0, it will be true. You can use this to check if a list is empty (false) or non empty (true). So you don’t need an equal sign, you can just say

if a:

you don’t need

if a == True:
#or
if a > 0:

Secondly, you’ll need to check that paths[node] is non-empty first, so you need to reverse the order of your if statement. This is because you want to check if it’s non-empty first and then you want to check paths[node][-1] == node

5

Thank you so much! I found the solution.

1 Like
6

Can you tell me what [Learn Algorithm Design by Building a Shortest Path Algorithm] is showing/teaching in these 54 steps? So I can find a youtube video about it to understand more.

7

I haven’t actually done this new curriculum yet, so I couldn’t say.

The way these are designed though is that you will learn many smaller details (the if... and... structure here) while putting together a bigger CS concept (Shortest Path algorithm)

So you’re not really just learning 1 thing, but learning many small things in the context of a larger thing. You could read about Shortest Path algorithms here:
https://www.geeksforgeeks.org/shortest-path-algorithms-a-complete-guide/

1 Like
8

I’m not understanding this one at all. I feel like the wording for a lot of this section isn’t so clear.

My code:

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

Does not pass.

9

Please open a new topic for your question

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.

11

Did you read this solution?