This week's book giveaway is in the Servlets forum.
We're giving away four copies of Murach's Java Servlets and JSP and have Joel Murach on-line!
See this thread for details.
The moose likes Beginning Java and the fly likes Graphs and Dijktra's algorithm.. Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Graphs and Dijktra Watch "Graphs and Dijktra New topic
Author

Graphs and Dijktra's algorithm..

Justin Fox
Ranch Hand

Joined: Jan 24, 2006
Posts: 802
ok...

in DA (dijktras alg.) ..

you have nodes and edges..

now can edges be represented by different pointers

within the node class that point to other nodes,

and just each have each pointer have a weight:int?

and once i get that hard-coded, how to i go about traversing

the graph radomly?

Justin


You down with OOP? Yeah you know me!
Justin Fox
Ranch Hand

Joined: Jan 24, 2006
Posts: 802
please help?
Burkhard Hassel
Ranch Hand

Joined: Aug 25, 2006
Posts: 1274
Hi,

did you check this?

http://en.wikipedia.org/wiki/Dijkstra's_algorithm


Bu.


all events occur in real time
Shaan Shar
Ranch Hand

Joined: Dec 27, 2005
Posts: 1249

Originally posted by Burkhard Hassel:
Hi,

did you check this?

http://en.wikipedia.org/wiki/Dijkstra's_algorithm


Bu.


Thankx Bu,

You have gave a good link....


The Best way to predict your future is to create it - Every great individual common man
Burkhard Hassel
Ranch Hand

Joined: Aug 25, 2006
Posts: 1274
You have gave a good link....


Normally I wouldn't post such links, as somebody could think, I would fool him/her.
But in this case I just looked and saw some pseudo code, that might be helpful.


Yours,
Bu.
Justin Fox
Ranch Hand

Joined: Jan 24, 2006
Posts: 802
ok ok, im just trying to get every possible path,

but im running to problems...

here is my code;



im trying to keep traversing from a until every node is Null,
meaning that all of its paths have been traveled...

but say i want to go ACF

ok, now A C and F's one pointer are set null.

but if wanted to go ABCF, i couldnt

cause C's one pointer is null...

how do i go about fixing this, or is there a better way?

Thanks A lot,

Justin
Steve Fahlbusch
Bartender

Joined: Sep 18, 2000
Posts: 557
    
    7

Well a better approach might be implementing the algorithm as presented in the link submitted by 'Bu' (oh, and Bu - that really is a quite good reference to Dijkstra's Algorithm).

Your approach seems to be missing the weight of the vertices (or maybe i'm missing something).

As to traversing, the link also supplies the pseudocode for iterating and obtaining the (or one of the) shortest path.

One way that seems to help in understanding (and hence implementation) is to do this on paper and note how you would sovle this by hand (or if you are required to implement DA, then how you would solve this by hand using the DA.
Justin Fox
Ranch Hand

Joined: Jan 24, 2006
Posts: 802
I re-did the application, with 2D array...

and did dijkstra's with a triple nested for loop...

worked quite well actually...

Justin
Steve Fahlbusch
Bartender

Joined: Sep 18, 2000
Posts: 557
    
    7

Congratulations!
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
 
subject: Graphs and Dijktra's algorithm..
 
Similar Threads
mvc design problem
Swing Graph Utilities (Graph = Nodes and Edges)
Dijkstra's problem
Vector cannot be private?
Displaying a graph