Python - Dijkstra的算法

Question

我需要在Python中實現Dijkstra的算法。但是，我必須使用2D數組來保存三條信息 - 前導，長度和未訪問/訪問。 我知道C可以使用結構，雖然我被困在如何在Python中做類似的事情，但我被告知這是可能的，但我不知道是誠實的

Answer 1

正如上面提到的，你可以使用一個對象的實例。

這位作者在Python中有一個非常令人信服的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 

self.known，self.distance ...是那些信息。他沒有在構造函數中設置這些（init），但稍後設置它們。在Python中，您可以使用點符號訪問屬性。 for examle：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，這對於保持結構類化合物類型，而自己的行爲，而是一個名爲成員特別爽：XXX = collections.namedtuple('XXX', 'predecessor length visited')。

用XXX(predecessor, length, visited)創建一個。

Answer 4

Python是面向對象的語言。所以想想它就像從C中的Structs轉移到C++的類中一樣。你也可以在Python中使用相同的類結構。

Answer 5

或者你可以簡單地使用元組或字典的二維數組裏面：

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)