Python - Dijkstraのアルゴリズム

Question

DijkstraのアルゴリズムをPythonで実装する必要があります。しかし、私は2D配列を使用して、前身、長さ、未訪問/訪問の3つの情報を保持する必要があります。 私はC言語で構造体を使うことができますが、私はPythonでこれと同様のことをすることができますが、それは可能だと言われていますが、正直であるとは思わないです

Answer 1

前述したように、あなたは、オブジェクトのインスタンスを使用することができます。

この著者はPythonでDijkstrasをかなり説得力のある方法で実装しています。

# 
# 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 ...これらはすべてpublicです。

Answer 2

Pythonオブジェクトあなたは大丈夫でしょう。

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)で1つを作成します。

Answer 4

Pythonはオブジェクト指向言語です。だから、C言語のStructsからC++のクラスに移行するのが好きです。 Pythonでも同じクラス構造を使うことができます。

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)