Python - Алгоритм Дейкстры

Question

Мне нужно реализовать Алгоритм Дейкстры в Python. Тем не менее, я должен использовать 2D-массив для хранения трех частей информации - предшественника, длины и невнимания/посещения. Я знаю, что в C a Struct можно использовать, хотя я зациклен на том, как я могу сделать аналогичную вещь в Python, мне говорят, что это возможно, но я не знаю, чтобы быть честным

Answer 1

Как уже упоминалось выше, вы можете использовать экземпляр объекта.

Этот автор имеет довольно убедительную реализацию на Python на Dijkstras в 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) 

Обратите внимание эти фрагменты информации удерживаемый "в объекте, он строит по телефону Algorithms.Entry(). Запись является классом и определяется следующим образом:

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 

Самостоятельное, самодостаточное ... это те части информации. Он не устанавливает эти явные в конструкторе (init), но устанавливает их позже. В Python вы можете получить доступ к атрибутам с точечной нотацией. для примера: myObject = Entry(). myObject.known, myObject.distance ... все они общедоступны.

Answer 2

Инкапсулировать эту информацию в объект Python и все должно быть в порядке.

Answer 3

Создайте для этого класс.

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

Или используйте collections.namedtuple, что особенно здорово для проведения STRUCT подобных составных типов без собственного поведения, но названных члены: XXX = collections.namedtuple('XXX', 'predecessor length visited').

Создайте с XXX(predecessor, length, visited).

Answer 4

Python - объектно-ориентированный язык. Поэтому подумайте об этом, перейдя от Structs в C к классам C++. Вы можете использовать ту же структуру классов и в Python.

Answer 5

Или вы можете просто использовать кортежи или словари внутри 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)