[Python-de] dijkstra algorithmus

[Christian Assing]

Hallo Andi,

Schau dir mal die networkx Library an http://networkx.lanl.gov/ . Diese Lib hat viele Funktionen zur Graphen Berechnung. 

Lg,
Chris


Von meinem iPad gesendet

Am 18.02.2012 um 18:16 schrieb sackbard <sackbard at googlemail.com>:

> 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
> 
> _______________________________________________
> python-de maillist  -  python-de at python.org
> http://mail.python.org/mailman/listinfo/python-de
>