Implementing Dijkstra’s Algorithm Into Python

Tutorial: Implementing Dijkstra’s Algorithm Into Python

Step 1:

The first aspect you need to implement Dijkstra’s Algorithm into Python is to create an excel spreadsheet that has the distances of all of your points. Rows will either be the origin or the destination with columns being the other. First, you will need to fill in every point that is the same as 0. For example, where the point starts at location 11 and ends at location 11. This way Python will know that it is at the correct point. Next fill in all of the actual distances between the locations that connect. You will need to do this for both origin and destination. So, if the distance between location 12 and 17 is 85.3 then in the point that starts at 12 and ends at 17, in addition to the point that starts at 17 and ends at 12 you will fill in 85.3. Last, you need to fill in the points that do not connect with a number significantly larger than any distance. For example, if your distances are around 100, then you could fill it in the 100,000. That way there is no chance that the shortest path will lead you through paths that do not connect.

Step 2:

You will next need to import your spreadsheet into python and then turn the spreadsheet into a dictionary so it can be used in Dijkstra’s Algorithm. First, you need to import xlrd in order to import the spreadsheet. Xlrd is just a way to read data from excel spreadsheets. Next you will make the xlrd into an array that numbers the data properly from the spreadsheet. Then you will turn the array into a dictionary, allowing it to be used in Dijkstra’s Algorithm. The code for all of this is below with map1 being the spreadsheet, worksheet being the xlrd from workbook, practice being the array and distances being the dictionary.

 import xlrd
 import xlwt as xlwt

 workbook = xlrd.open_workbook('map1.xls')
 workbook = xlrd.open_workbook('map1.xls', on_demand = True)
 worksheet = workbook.sheet_by_index(0)

 practice = []
 for col in range(0, worksheet.ncols):
    practice.append([])
    for row in range(0, worksheet.nrows):
        practice[-1].append(worksheet.cell_value(col, row))

 distances = {}
 for i in range(0, len(practice)):
    connect = {}
    for j in range(0, len(practice[i])):
        if practice[i][j] != 0:
            if practice[i][j] != 100000:
                connect[j+1] = practice[i][j]

    distances[i+1] = connect