Learn algorithm design by building a shortest path algorithm step - 50

Python
1

Can you all help me with this?

image
image757Ă—851 86.3 KB

2

Hi.

Instead of a screenshot, can you include actual code, its easieier for campers to work with.

1 Like
3

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.

1 Like
4 
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]
5

Can you think of a way to simplify this logic?

Please provide a link to the step you are working on.

6

I’ve edited your code for readability. When you enter a code block into a forum post, please precede it with a separate line of three backticks and follow it with a separate line of three backticks to make it easier to read.

You can also use the “preformatted text” tool in the editor (</>) to add backticks around text.

Pre-formatted-text
Pre-formatted-text1356Ă—380 401 KB

See this post to find the backtick on your keyboard.
Note: Backticks (`) are not single quotes (').