[Python-de] dijkstra algorithmus

[sackbard]

Hallo Python Community,

bin neu in der Liste und hab natürlich gleich eine Frage. Ich versuche
den dijkstra algorithmus in Python zu implementieren. Gegeben sind zwei
Dateien: die network.txt die die distanzen der einzelnen nodes angibt
und die route.txt die mir anfangs und endpunkt ausgibt.

Beispiel network.txt (in diesem Beispiel nodes A-G):
0,2,4,1,6,0,0
2,0,0,0,5,0,0
4,0,0,0,0,5,0
1,0,0,0,1,1,0
6,5,0,1,0,5,5
0,0,5,1,5,0,0
0,0,0,0,5,0,0

Beispiel route.txt:
B>F

Am ende soll eine neue txt datei erstellt werden welche die route und
die total path length enthält.

Bis auf den letzten Schritt funktioniert auch alles soweit (python 3.1.1). Ich bin nur
noch nicht dahinter gekommen wie ich am Ende am besten die Route und die
Total path length berechne. Hatte überlegt den weg vom letzten zum
ersten node einfach zurückzugehen aber das scheint mir umständlich und
kompliziert.

Hier das script soweit ich das hinbekommen habe:

import sys

invalid_node = -1

class Node:
    previous = invalid_node
    distFromSource = sys.maxsize
    visited = False

#print ("\nReading the file into a list.")
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)
   
   

# 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)
 
#print ("Start node: " + str(startNode))
#print ("End node: " + str(endNode))

# set currentNode to startNode
currentNode = startNode

# create another 2d array with previous node, distFromSource and visited
# use sys.maxint for distFromSource


nodeTable = [] # array containing nodeTable visited/unvisited,prevNode
and distFromSrc
i = 0

while i <= numberOfNodes:
    nodeTable.append(Node())
    i += 1


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


#write a function to find the neighbour 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


#print ("\nCurrent Neighbours (of node " + str(currentNode) + "): ")
currentNeighbours = findNeighbours(currentNode)

#print (currentNeighbours)


# go through currentNeighbour and see if they have been visited or not
# set dustFromSource and previousNode for unvisited
def checkNeighbours():
    for neighbour in currentNeighbours:
        if nodeTable[neighbour].visited == True:
            pass
            #print ("True")
        else:
            # calculate their tentative distances from starting node
            # add distFromSource from currentNode with distance between
currentNode and neighbour
            # check if less than current
            newDistance = nodeTable[currentNode].distFromSource +
network[currentNode][neighbour]

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

checkNeighbours()
#printNodeTb()

# go through all distances of unvisited, find lowest and mark as visited
def setNewCurrentNode():
    global currentNode  
    index = 0
    currentDist = sys.maxsize

   

    for node in nodeTable:
        if node.visited == False and node.distFromSource < currentDist:
            currentNode = index
            currentDist = node.distFromSource
        index+=1
       
    nodeTable[currentNode].visited = True
    print ("\nNew Current Node: " + str(currentNode))




setNewCurrentNode()

#total path length
tpl = 0

f = open("09023429spf.txt", "w")
f.write(str(chr(startNode+65)))

# check if destination node reached
while currentNode != endNode:
   
    #print ("\nCurrent Neighbours (of node " + str(currentNode) + "): ")
    currentNeighbours = findNeighbours(currentNode)
    #print (currentNeighbours)
   
    checkNeighbours()
    f.write(str(chr(currentNode+65)))
   
    setNewCurrentNode()
    #add total path length
    tpl += nodeTable[nodeTable[currentNode].previous].distFromSource
   
f.write(str(chr(endNode+65)))
f.write(" " + str(tpl))
f.close()


print ("\nTotal path length: " + str(tpl) + "\n")
for node in nodeTable:
    print (str(node.previous) + " | " + str(node.distFromSource) + " | "
+ str(node.visited))


Wäre für jede Hilfe dankbar.

Dankeschön.

Gruß
Andi