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.append( 0 )
else:
w.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 )

 

[Peter Hansen]

I need that someone help me.

I need to program the dijkstra algorithm by object oriented.

I'll send my code.

Thanks, but you haven't asked a question. Thus it sounds
as though you are simply asking for someone to make your
code work correctly. Or maybe you're asking for someone
to convert it from the style shown to an object oriented
approach.

Either way, it sounds a lot like this is a homework question
for school, so I really hope nobody is going to just do the
work for you, since you won't learn anything that way.

Please reconsider what you are trying to do and ask a
specific question, demonstrating that you have made a
reasonable attempt to solve the problem yourself first.

-Peter

 

[Dave Benjamin]

I need that someone help me.

No, you need to do your own work like everybody else.

I need to program the dijkstra algorithm by object oriented.

No, you don't, and you should tell your professor to unsubscribe from
silver-bullet OO hype and realize that OO has little to add to
mathematical problems like this.

Dijkstra must be rolling in his grave.

Dave