dijkstra algorithm by object oriented

From: Ricardo Batista (batista.ric_at_iol.pt)
Date: 11/04/04 

To: <python-list@python.org>
Date: Thu, 4 Nov 2004 12:05:37 -0000

I need that someone help me.

I need to program the dijkstra algorithm by object oriented.

I'll send my code.

#!/usr/bin/env python
# -*- encoding: latin -*-

NIL = []
INF = 9999

G = { "Vertices" : [ 0, 1, 2, 3, 4, 5, 6 ],
      "Adjacentes" : { 0 : {1: 5, 2: 4},
              1 : {3: 7, 5: 3},
              2 : {4: 7},
              3 : {2: 6},
              4 : {5: 2},
              5 : {6: 3},
              6 : {}
              }
      } # definição do grafo

# 0 1 2 3 4 5 6
W = [ [0 , 5 , 4 , INF, INF, INF, INF],
      [INF, 0 , INF, 7 , INF, 3 , INF],
      [INF, INF, 0 , INF, 7 , INF, INF],
      [INF, INF, 6 , 0 , INF, INF, INF],
      [INF, INF, INF, INF, 0 , 2 , INF],
      [INF, INF, INF, INF, INF, 0 , 3 ],
      [INF, INF, INF, INF, INF, INF, 0 ] ]

def adjMatrix( ):
    w = NIL
    for i in G["Vertices"]:
        w.append( [] )
    for i in G["Vertices"]:
        for j in G["Vertices"]:
            if i == j:
                w[i].append( 0 )
            else:
                w[i].append( INF )
    for y in range(len( w )):
        aux1 = G[ "Adjacentes" ][ y ].keys( )
        aux2 = G[ "Adjacentes" ][ y ].values( )
        for i in range( len( w ) ):
            for j in range( len( aux1 ) ):
                if i == aux1[ j ]:
                    w[ y ][ i ] = aux2[ j ]
    return w

d = {}
pi = {}
Q = {}

def initialize_Single_Source( G, s ):
    for v in G[ "Vertices" ]:
        d[ v ] = INF
        pi[ v ] = NIL
    d[ s ] = 0

def relax( u, v, w ):
    if d[ v ] > d[ u ] + w[ u ][ v ]:
        d[ v ] = d[ u ] + w[ u ][ v ]
        pi[ v ] = u

def dijkstra( G, w, s ):
    initialize_Single_Source( G, s )
    S = []
    Q = G[ "Vertices" ]
    while Q != []:
        u = extract_Min( Q )
        S.append( u )
        for v in G[ "Adjacentes" ]:
            relax(u, v, w)
    print "d:",d
    print "pi:",pi

def extract_Min( Q ):
    m = min( Q )
    Q.remove( m )
    return m

dijkstra( G, adjMatrix(), 0 ) 

---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.788 / Virus Database: 533 - Release Date: 01-11-2004