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

Python
1

Tell us what’s happening:

I understood the steps up to this one, but now I feel lost reading the instructions. My first question is what is graph[current]? Is it a list we are iterating over with the user-input nodes? So it looks like my_graph, but it contains different values? Secondly, why is the distance of the neighbor node plus the distance of current the ‘second item in the tuple’? What tuple, aren’t there several in the list ‘graph’?

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)

# User Editable Region

        for node, distance in graph[current]:
            if second item in the processed tuple + current < the first item in the processed tuple:
                pass

# User Editable Region

    print(f'Unvisited: {unvisited}\nDistances: {distances}\nPaths: {paths}')
    
#shortest_path(my_graph, 'A')

Your browser information:

User Agent is: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/127.0.0.0 Safari/537.36

Challenge Information:

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

2

graph is my_graph

You can see at the bottom of your code that you call this function and pass it my_graph in place of the first argument which becomes graph within the function.

So, it’s a dictionary of lists containing tuples.

3

Hey there can you help me with step 50

image
image757×851 86.9 KB

4

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 Help button located on the challenge. This button only appears if you have tried to submit an answer at least three times.

image
image622×306 7.96 KB

The 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.