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

Python
1

Tell us what’s happening:

Can someone walk through the logic of this function? This one was brutal for me. Does anyone know if there exists an official FCC video that steps through what is happening across each line of this function?

I certainly got lost with all of the indexing and “neighbor node” and “current node”, etc. I am hoping a video exists of someone explaining the theory. Thanks!

Thanks in advance!

Your code so far


# User Editable Region

my_graph = {
    'A': [('B', 5), ('C', 3), ('E', 11)],
    'B': [('A', 5), ('C', 1), ('F', 2)],
    'C': [('A', 3), ('B', 1), ('D', 1), ('E', 5)],
    'D': [('C',1 ), ('E', 9), ('F', 3)],
    'E': [('A', 11), ('C', 5), ('D', 9)],
    'F': [('B', 2), ('D', 3)]
}

def shortest_path(graph, start, target = ''):
    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)
    
    targets_to_print = [target] if target else graph
    for node in targets_to_print:
        if node == start:
            continue
        print(f'\n{start}-{node} distance: {distances[node]}\nPath: {" -> ".join(paths[node])}')
    
    return distances, paths
    
shortest_path(my_graph, 'A')

# User Editable Region

Your browser information:

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/137.0.0.0 Safari/537.36 Edg/137.0.0.0

Challenge Information:

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

2

I don’t think there is an official video, but be assured, the shortest path algorithm is not the easiest to follow, you may benefit from finding any video on the shortest path algorithm

3

thank you for the reassurance. I felt quite insignificant lol.

for any who may stumble on this, I plugged this into claude and asked to be walked through the solution, step by step. Not bad actually. It is still difficult, but the pseudo code and explanation is helping me grasp the concepts.