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)