PROJECT EULER SOLUTION # 83

Project Euler Problem # 83

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to 2297.

Find the minimal path sum, in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by moving left, right, up, and down.

Project Euler Solution # 83 in Python

numberOfNodes = 80

class GraphNode:
    row = 0
    col = 0
    data = 0
    shortestDistance=0 # distance from source
    parent=None
    adjacencyList = []

    def __init__(self, row, col, data):
        self.row = row
        self.col = col
        self.data = data
        self.shortestDistance=0
        parent=None

    def printGraphNode(self):
        print(self.data),

    def updateAdjacencyList(self, nodeList):
        self.adjacencyList=[]
        if self.row - 1 != -1:
            self.adjacencyList.append(nodeList[self.row - 1][self.col])
        if self.row + 1 != len(nodeList):
            self.adjacencyList.append(nodeList[self.row + 1][self.col])
        if self.col - 1 != -1:
            self.adjacencyList.append(nodeList[self.row][self.col - 1])
        if self.col + 1 != len(nodeList):
            self.adjacencyList.append(nodeList[self.row][self.col + 1])


    def printAdjacencyList(self):
        for i in range(len(self.adjacencyList)):
            print self.adjacencyList[i].data,


# class ended here...
def initialiseSingleSource(nodeList,source):
    for i in range(len(nodeList)):
        for j in range(len(nodeList[i])):
            nodeList[i][j].shortestDistance=2147483647
            nodeList[i][j].parent=None
    source.shortestDistance=source.data

def extractMin(Q):
    mini=0
    min=Q[0].shortestDistance
    for i in range(len(Q)):
        if Q[i].shortestDistance < min :
            min=Q[i].shortestDistance
            mini=i
    u=Q[mini]
    Q.remove(Q[mini])
    return u

def relax(u,v):
    if v.shortestDistance > u.shortestDistance+v.data:
        v.shortestDistance=u.shortestDistance+v.data
        v.parent=u

def dijkstra(nodeList,source):
    initialiseSingleSource(nodeList,source)
    Q=[]
    for i in range(len(nodeList)):
        for j in range(len(nodeList[i])):
            Q.append(nodeList[i][j])

    while len(Q) != 0 :
        u=extractMin(Q)
        for i in range(len(u.adjacencyList)):
            relax(u,u.adjacencyList[i])

test_file = open("a.txt", "r+")

myList = test_file.read().split('\n')

listLen=len(myList)
for i in range(listLen):
    myList.append(myList[0].split(','))
    myList.remove(myList[0])

for i in range(numberOfNodes):
    for j in range(numberOfNodes):
        myList[i][j] = int(myList[i][j])

nodeList = []
for i in range(numberOfNodes):
    nodeList.append([])
    for j in range(numberOfNodes):
        nodeList[i].append(GraphNode(i, j, myList[i][j]))

for i in range(numberOfNodes):
    for j in range(numberOfNodes):
        nodeList[i][j].updateAdjacencyList(nodeList)

dijkstra(nodeList,nodeList[0][0])

print "answer is : ",nodeList[numberOfNodes-1][numberOfNodes-1].shortestDistance