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

Question

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

Answer 1

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

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

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

Создать с помощью XXX(predecessor, length, visited).

Answer 2

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

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

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

Answer 3

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

Answer 4

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

Answer 5

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