dijkstra algorithm by object oriented

[Ricardo Batista]

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