Python - Algorithme de Dijkstra

Question

J'ai besoin de mettre en œuvre l'algorithme de Dijkstra en Python. Cependant, je dois utiliser un tableau 2D pour contenir trois éléments d'information - prédécesseur, longueur et non visité/visité. Je sais que dans C un Struct peut être utilisé, bien que je sois bloqué sur comment je peux faire une chose similaire en Python, on me dit que c'est possible mais je n'ai aucune idée d'être honnête

Answer 1

Comme mentionné ci-dessus, vous pouvez utiliser une instance d'un objet.

Cet auteur a une implémentation Python assez convaincante de Dijkstras en python.

# 
# This file contains the Python code from Program 16.16 of 
# "Data Structures and Algorithms 
# with Object-Oriented Design Patterns in Python" 
# by Bruno R. Preiss. 
# 
# Copyright (c) 2003 by Bruno R. Preiss, P.Eng. All rights reserved. 
# 
# http://www.brpreiss.com/books/opus7/programs/pgm16_16.txt 
# 
class Algorithms(object): 

    def DijkstrasAlgorithm(g, s): 
     n = g.numberOfVertices 
     table = Array(n) 
     for v in xrange(n): 
      table[v] = Algorithms.Entry() 
     table[s].distance = 0 
     queue = BinaryHeap(g.numberOfEdges) 
     queue.enqueue(Association(0, g[s])) 
     while not queue.isEmpty: 
      assoc = queue.dequeueMin() 
      v0 = assoc.value 
      if not table[v0.number].known: 
       table[v0.number].known = True 
       for e in v0.emanatingEdges: 
        v1 = e.mateOf(v0) 
        d = table[v0.number].distance + e.weight 
        if table[v1.number].distance > d: 

         table[v1.number].distance = d 
         table[v1.number].predecessor = v0.number 
         queue.enqueue(Association(d, v1)) 
     result = DigraphAsLists(n) 
     for v in xrange(n): 
      result.addVertex(v, table[v].distance) 
     for v in xrange(n): 
      if v != s: 
       result.addEdge(v, table[v].predecessor) 
     return result 
    DijkstrasAlgorithm = staticmethod(DijkstrasAlgorithm) 

Avis ces informations sont « lieu » dans l'objet, il est construit en appelant Algorithms.Entry(). L'entrée est une classe et est définie comme ceci:

class Entry(object): 
    """ 
    Data structure used in Dijkstra's and Prim's algorithms. 
    """ 

    def __init__(self): 
     """ 
     (Algorithms.Entry) -> None 
     Constructor. 
     """ 
     self.known = False 
     self.distance = sys.maxint 
     self.predecessor = sys.maxint 

Les auto-notés, autodistance ... sont ces éléments d'information. Il ne les définit pas explicitement dans le constructeur (init) mais les définit plus tard. En Python, vous pouvez accéder aux attributs avec notation par points. par exemple: myObject = Entry(). myObject.known, myObject.distance ... ils sont tous publics.

Answer 2

Encapsuler cette information dans un objet Python et ça devrait aller.

Answer 3

Créez une classe pour cela.

class XXX(object): 
    def __init__(self, predecessor, length, visited): 
     self.predecessor = predecessor 
     self.length = length 
     self.visited = visited 

Ou utilisez collections.namedtuple, ce qui est cool en particulier pour la tenue de types de composés comme struct sans comportement, mais les membres nommés: XXX = collections.namedtuple('XXX', 'predecessor length visited').

Créez-en un avec XXX(predecessor, length, visited).

Answer 4

Python est un langage orienté objet. Donc, pensez-y comme passer de Structs in C à Classes of C++. Vous pouvez également utiliser la même structure de classe en Python.

Answer 5

Ou vous pouvez simplement utiliser tuples ou des dictionnaires dans votre tableau 2d:

width=10 
height=10 

my2darray = [] 
for x in range(width): 
    my2darray[x]=[] 

for x in range(width): 
    for y in range(height): 
     #here you set the tuple 
     my2darray[x][y] = (n,l,v) 
     #or you can use a dict.. 
     my2darray[x][y] = dict(node=foo,length=12,visited=False)