CODEWITHSUNDEEP
pythondijkstra
user612041
user612041

Reputation: 215

Python - Dijkstra's Algorithm

I need to implement Dijkstra's Algorithm in Python. However, I have to use a 2D array to hold three pieces of information - predecessor, length and unvisited/visited. I know in C a Struct can be used, though I am stuck on how I can do a similar thing in Python, I am told it's possible but I have no idea to be honest

Upvotes: 0

Views: 5776

Answers (5)

brianray
brianray

Reputation: 1169

As mentioned above, you can use an instance of an object.

This author has a pretty convincing python implementation of Dijkstras in 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)

Notice those pieces of information are 'held' in the object he is constructing by calling Algorithms.Entry(). Entry is a class and is defined like this:

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

The self.known, self.distance... are those pieces of information. He does not set these explicit in the constructor (init) but sets them later. In Python you can access attributes with dot notation. for examle: myObject= Entry(). the myObject.known, myObject.distance... they are all public.

Upvotes: 1

user199977
user199977

Reputation:

Or you can simply use tuples or dictionaries inside your 2d array:

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)

Upvotes: 1

Neo
Neo

Reputation: 13891

Python is object oriented language. So think of it like moving from Structs in C to Classes of C++. You can use the same class structure in Python as well.

Upvotes: 0

user395760
user395760

Reputation:

Create a class for it.

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

Or use collections.namedtuple, which is particular cool for holding struct-like compound types without own behaviour but named members: XXX = collections.namedtuple('XXX', 'predecessor length visited').

Create one with XXX(predecessor, length, visited).

Upvotes: 2

duffymo
duffymo

Reputation: 308763

Encapsulate that information in a Python object and you should be fine.

Upvotes: 1

Related Questions