[Python-de] dijkstra algorithmus

[sackbard]

Hallo Peter, hallo Christian,

vielen Dank für Eure Mails. Insbesondere die von dir, Peter, hat mir
sehr weiter geholfen. Habe versucht das entsprechend Deinen Kommentaren
umzustellen. Das mit der total path length war eine blöde Frage von mir.
Habe die Info ja schon...schätze ich habe den Überblick verloren. Du
hast ja sicher gemerkt das ich noch blutiger Anfänger bin insofern freue
ich mich über jegliche weiteren Verbesserungsvorschläge. Ansonsten unten
stehend die Lösung für meine Implementierung.

Gibt es einen Grund open(...) as file zu nutzen anstatt des file=open()
etc oder ist es einfach nur kürzer?

Gruß
Andi
_________


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 the total path length
f.write(" " + str(nodeTable[currentNode].distFromSource))
f.close()