Python - Dijkstra 's 알고리즘

Question

Dijkstra 's Algorithm을 Python으로 구현해야합니다. 그러나 전 배열, 길이 및 비 방문/방문의 세 가지 정보를 담기 위해 2D 배열을 사용해야합니다. 내가 파이썬에서 비슷한 일을 할 수있는 방법에 붙어 있어요하지만 내가 구조체를 사용할 수 있습니다 C 알고,

Answer 1

, 당신은 개체의 인스턴스를 사용할 수 있습니다.

이 저자는 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 ...는 정보입니다. 그는 생성자 (초기화)에서 명시 적으로 설정하지는 않지만 나중에 설정합니다. 파이썬에서는 도트 표기법으로 속성에 액세스 할 수 있습니다. testle에 대한 : myObject = Entry(). myObject.known, myObject.distance ... 모두 공개입니다.

Answer 2

파이썬 객체에 해당 정보를 캡슐화 나는 그것이 가능하다고 이야기하고 있지만 솔직히 아무 생각이 없다 너 괜찮을거야.

Answer 3

클래스를 만듭니다. XXX = collections.namedtuple('XXX', 'predecessor length visited') : 자신의 행동하지만라는 이름의 멤버없이 구조체와 같은 복합 유형을 유지 특히 멋지다

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

또는 사용 collections.namedtuple.

XXX(predecessor, length, visited)으로 하나 만듭니다.

Answer 4

파이썬은 객체 지향 언어입니다. C의 Structs에서 C++의 클래스로 이동하는 것과 같습니다. 파이썬에서도 같은 클래스 구조를 사용할 수 있습니다.

Answer 5

또는 당신은 단순히 2 차원 배열 내부 튜플 또는 사전을 사용할 수 있습니다 : 위에서 언급 한 바와 같이

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)