472,807 Members | 3,161 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 472,807 software developers and data experts.

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 )
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 4140
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

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.

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.

Jul 18 '05 #3

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

by: ThanhVu Nguyen | last post by:
Hi all, I need recommendation for a very fast shortest path algorithm. The edges are all directed, positive weights. Dijkstra shortest path will solve it just fine but the if the graph is not...
by: bpontius | last post by:
The GES Algorithm A Surprisingly Simple Algorithm for Parallel Pattern Matching "Partially because the best algorithms presented in the literature are difficult to understand and to implement,...
by: A_StClaire_ | last post by:
implemented Dijkstra's algorithm as follows. plz pour on the negative criticism cuz I know I have a ton to learn. oh, before you flame me regarding the language, my class was told to do this in...
by: Ook | last post by:
This is probably a bit OT, as I'm not looking for a c++ implementaiton of Dijkstra's algorithm, rather I'm just trying to understand it (is there a better place then here to ask this question?)....
by: arlef | last post by:
Can somebody please explain and provide pseudocode for the Dijkstra algorithm? I'm trying to implement the Dijkstra shortest path algorithm. However, I'm finding it extremely difficult to...
by: Josh Zenker | last post by:
I've been working on an implementation of Dijkstra's algorithm on and off for the past few days. I thought I was close to being finished, but clearly I've done something wrong. I'm not a very...
by: Ganon11 | last post by:
Hey guys, I'm back, and with another FUN question! My latest homework asks this question: "Suppose all the edge weights in a graph are integers between 1 and |E|. How fast can Dijkstra's...
by: shashankbs | last post by:
Given a topology and a certain node X, find the shortest path tree with X as the root. * Input: a topology file similar to the following (which is a three-node ring) ...
by: Glenton | last post by:
Hi All Here is a very simple little class for finding a shortest route on a network, following Dijkstra's Algorithm: #!/usr/bin/env python #This is meant to solve a maze with Dijkstra's...
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 2 August 2023 starting at 18:00 UK time (6PM UTC+1) and finishing at about 19:15 (7.15PM) The start time is equivalent to 19:00 (7PM) in Central...
by: erikbower65 | last post by:
Using CodiumAI's pr-agent is simple and powerful. Follow these steps: 1. Install CodiumAI CLI: Ensure Node.js is installed, then run 'npm install -g codiumai' in the terminal. 2. Connect to...
by: linyimin | last post by:
Spring Startup Analyzer generates an interactive Spring application startup report that lets you understand what contributes to the application startup time and helps to optimize it. Support for...
by: Taofi | last post by:
I try to insert a new record but the error message says the number of query names and destination fields are not the same This are my field names ID, Budgeted, Actual, Status and Differences ...
by: DJRhino1175 | last post by:
When I run this code I get an error, its Run-time error# 424 Object required...This is my first attempt at doing something like this. I test the entire code and it worked until I added this - If...
by: Rina0 | last post by:
I am looking for a Python code to find the longest common subsequence of two strings. I found this blog post that describes the length of longest common subsequence problem and provides a solution in...
by: lllomh | last post by:
How does React native implement an English player?
by: Mushico | last post by:
How to calculate date of retirement from date of birth
by: DJRhino | last post by:
Was curious if anyone else was having this same issue or not.... I was just Up/Down graded to windows 11 and now my access combo boxes are not acting right. With win 10 I could start typing...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.