Linked Questions

Popular Questions

I am struggling to implement Dijkstra's algorithm into my GUI that I have made. In my GUI you are able to select a start node and an end node on a grid and then I am hoping that Dijkstra's algorithm will solve the shortest path between the two. I have pasted the code for my Dijkstra's and then just made it so that the start node and end node are in the opposite corners of the grid. When I run the program currently it is giving me an error about an index being out of range and I do not understand why. Thanks for any help.

The error message is:

Traceback (most recent call last):
  File "./dijkstra.py", line 110, in <module>
    dijkstra(grid,start_node,finish_node)
  File "./dijkstra.py", line 36, in dijkstra
    paths = unseenNodes[min_node_row][min_node_column][3]
IndexError: list index out of range

The Code:

def dijkstra(graph,start,goal):
    shortest_distance = []
    previous_node = []
    unseenNodes = graph
    infinity = 9999999
    path = []

    for row in unseenNodes:
        for node in row:
            shortest_distance.append(infinity)
    shortest_distance[start] = 0


    while unseenNodes:
        minNode = None
        node_num = -1
        node_row = -1
        for row in unseenNodes:
            node_row += 1
            node_column = -1
            for column in row:
                node_column += 1
                node_num += 1
                if minNode is None:
                    minNode = column
                    min_node_row = node_row
                    min_node_column = node_column
                    minNode_num = node_num
                elif shortest_distance[node_num] < shortest_distance[minNode_num]:
                    minNode = column
                    min_node_row = node_row
                    min_node_column = node_column


        weight = 1
        paths = unseenNodes[min_node_row][min_node_column][3]
        print(unseenNodes[min_node_row][min_node_column])
        for childNode in paths:
            if weight + shortest_distance[minNode_num] < shortest_distance[childNode]:
                shortest_distance[childNode] = weight + shortest_distance[minNode]
                previous_node[childNode] = minNode
        del unseenNodes[min_node_row][min_node_column]
        unseenNodes[min_node_row].pop(min_node_column)

    currentNode = goal
    while currentNode != start:
        try:
            path.insert(0,currentNode)
            currentNode = previous_node[currentNode]
        except KeyError:
            print('Path not reachable')
            break
    path.insert(0,start)
    if shortest_distance[goal] != infinity:
        print('Shortest distance is ' + str(shortest_distance[goal]))
        print('And the path is ' + str(path))

#constants within code
black = (0, 0, 0)
white = (255, 255, 255)
grey = (125,125,125)
green = (0, 200, 0)
red = (200, 0, 0)
bright_red = (255,0,0)
bright_green = (0,255,0)
blue = (0,0,200)
yellow = (255,255,0)

grid_width = 40
grid_height = 40
cell = (grid_width, grid_height)

grid_margin = 5
distance_from_left = 500
distance_from_top = 100

#creates grid
grid = []
for y in range(10):
     row = []
     for x in range(10):
         row.append([x * (grid_width + grid_margin) + distance_from_left, y * (grid_height + grid_margin) + distance_from_top, white,[]])
     grid.append(row)

grid[0][0][2] = green
grid[9][9][2] = red

print(grid)

#work out start and finish node
start_node = ""
finish_node = ""
blocked_nodes = []
node_num = -1
for row in grid:
    for column in row:
        node_num += 1
        if column[2] == green:
            start_node = node_num
        elif column[2] == red:
            finish_node = node_num
        elif column[2] == grey:
            blocked_node = column
            blocked_nodes.append(blocked_node)

print(start_node)
print(finish_node)
print(blocked_nodes)

dijkstra(grid,start_node,finish_node)

Related Questions