dijkstra

gistfile1.py

import sys

invalid_node = -1

class Node (object):
    def __init__(self):
        self.previous = invalid_node
        self.distFromSource = sys.maxsize
        self.visited = False

#### FUNCTIONS / METHODS ####

#finds the neighbours of current node
def findNeighbours(currentNode):
    # find nearest neighbour of currentNode
    currentRow = network[currentNode]
    currentNeighbours = []
    i = 0

    for distance in currentRow:
        #get back the index number / position if distance = 0
        if distance != 0:
            #save the location
            currentNeighbours.append(i)
        i += 1    
    return currentNeighbours


# go through nodetable and add distance and previous if unvisited
def calculateTentative(nodeTable,currentNeighbours):
    for neighbour in currentNeighbours:
        if nodeTable[neighbour].visited == True:
            pass
        else:
            # calculate tentative distances, add distFromSource
            newDistance = nodeTable[currentNode].distFromSource + network[currentNode][neighbour]

            if (nodeTable[neighbour].distFromSource > newDistance):
                nodeTable[neighbour].distFromSource = newDistance
                nodeTable[neighbour].previous = currentNode
    return nodeTable

# go through all distances of unvisited, find the one with lowest dist
def setNewCurrentNode(nodeTable):
    nextNode = -1   
    index = 0
    nextDist = sys.maxsize

    for node in nodeTable:
        if node.visited == False and node.distFromSource < nextDist:
            nextNode = index
            nextDist = node.distFromSource
        index+=1
    return nextNode


def createNetworkTable():
    txtfile = open("network.txt", "r")
    numberOfNodes = 0

    network = [] # array containing array of values for each line

    # reading file line by line 
    for line in txtfile:
        # increment nodeCount
        numberOfNodes += 1
        
        # remove end chars
        line = line.replace("\n","")
        line = line.replace("\r","")

        # split by comma
        chars = line.split(",")
        ints = []

        # convert string to int
        for char in chars:
            ints.append(int(char))

        # append the list of ints to the array
        network.append(ints)
    return network

def readRoute():
    # read start (dist value = 0) and end node 
    route = open("route.txt", "r")

    for line in route:
        nodes = line.split(">")
        startNode = nodes[0]
        endNode = nodes[1]

    # get the ascii value and minus 65 
    startNode =(ord(startNode) - 65) 
    endNode =(ord(endNode) - 65)
 
    return startNode, endNode

def createNodeTable():
    # array containing nodeTable visited/unvisited,prevNode and distFromSrc
    nodeTable = [] 
    i = 0

    for i in range(len(network)):
        nodeTable.append(Node())

    # set distFromSource of startNode to 0
    nodeTable[startNode].distFromSource = 0
    return nodeTable



def calcRoute(nodetable,currentNode,startNode):
    route = []
    total_path_length = 0

    while True:
        route.append(currentNode)
        if currentNode == startNode:
            break
        currentNode = nodeTable[currentNode].previous
    
    route.reverse()
    route = "".join(chr(node+65) for node in route)
    return route

#### APPLICATION FLOW ####

#create network table
network = createNetworkTable()

#get startNode and endNode from file
startNode, endNode = readRoute()

# set currentNode to startNode
currentNode = startNode

# create Node table    
nodeTable = createNodeTable()



f = open("09023429spf.txt", "w")

# continue until desination reached
while currentNode != endNode:
    # get list of current neighbours
    currentNeighbours = findNeighbours(currentNode)
    # set current node as visited
    nodeTable[currentNode].visited = True
    # get new nodeTable
    nodeTable = calculateTentative(nodeTable,currentNeighbours)
    # set new current node
    currentNode = setNewCurrentNode(nodeTable)



# get the route solution     
route = calcRoute(nodeTable,currentNode, startNode)

f.write(route)
# add total path length
f.write(" " + str(nodeTable[currentNode].distFromSource))
f.close()