Implement the Shortest Path Algorithm - Step 19

Python
1

Tell us what’s happening:

Hi,
I’m just doing what the step asked:

You should assign paths[node_no] to be the current path to the current node, with the node_no (the neighbor) added at the end.
aka doing:

paths[node_no] = paths[current] + node_no

but it’s not working.

Your code so far

INF = float('inf')
adj_matrix = [
    [0, 5, 3, INF, 11, INF],
    [5, 0, 1, INF, INF, 2],
    [3, 1, 0, 1, 5, INF],
    [INF, INF, 1, 0, 9, 3],
    [11, INF, 5, 9, 0, INF],
    [INF, 2, INF, 3, INF, 0],
]

def shortest_path(matrix, start_node, target_node=None):
    n = len(matrix)
    distances = [INF] * n
    distances[start_node] = 0
    paths = [[node_no] for node_no in range(n)]
    visited = [False] * n

    for _ in range(n):
        min_distance = INF
        current = -1
        for node_no in range(n):
            if not visited[node_no] and distances[node_no] < min_distance:
                min_distance = distances[node_no]
                current = node_no

        if current == -1:
            break
        visited[current] = True


# User Editable Region

        for node_no in range(n):
            distance = matrix[current][node_no]
            if distance != INF and not visited[node_no]:
                new_distance = distances[current] + distance
                if new_distance < distances[node_no]:
                    distances[node_no] = new_distance
                    paths[node_no] = paths[current] + node_no

# User Editable Region

Your browser information:

User Agent is: Mozilla/5.0 (X11; Linux x86_64; rv:142.0) Gecko/20100101 Firefox/142.0

Challenge Information:

Implement the Shortest Path Algorithm - Step 19

2

What type of data is paths[current]?

3

that’s a number. I tried doing making a list for path:
paths[node_no] = [paths[current], node_no]
and
adding strings
paths[node_no] = str(paths[current]) + str(node_no)
but they simply didn’t work

4

Well, I had to do removed. thought I already tried it but turns out I didn’t. thanks

5

paths[node_no] is actually a list, because paths is a list of lists.

You can try testing bits of code in a separate editor to try things out when you are coding in a function like this: https://www.online-python.com/

paths = [[node_no] for node_no in range(5)]
print(paths)
paths[2] = paths[3] + 5
print(paths)

Here you can clearly see what paths is all about and the error when you try to add a number to it.

[[0], [1], [2], [3], [4]]
Traceback (most recent call last):
  File "main.py", line 6, in <module>
    paths[2] = paths[3] + 5
TypeError: can only concatenate list (not "int") to list
6

Glad you got it! However, please don’t post solution code to the forum

7

Sorry for doing that!

1 Like