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.