468,133 Members | 1,181 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,133 developers. It's quick & easy.

dijkstra algorithm by object oriented

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

Jul 18 '05 #1
2 3937
Ricardo Batista wrote:
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
Jul 18 '05 #2
Ricardo Batista wrote:
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
Jul 18 '05 #3

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

6 posts views Thread by ThanhVu Nguyen | last post: by
3 posts views Thread by A_StClaire_ | last post: by
3 posts views Thread by Ook | last post: by
1 post views Thread by arlef | last post: by
9 posts views Thread by Josh Zenker | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.