This week's book giveaway is in the Clojure forum.
We're giving away four copies of Clojure in Action and have Amit Rathore and Francis Avila on-line!
See this thread for details.
Win a copy of Clojure in Action this week in the Clojure forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Graphs and Dijktra's algorithm..

 
Justin Fox
Ranch Hand
Posts: 802
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Justin Fox
Ranch Hand
Posts: 802
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
please help?
 
Burkhard Hassel
Ranch Hand
Posts: 1274
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

did you check this?

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


Bu.
 
Shaan Shar
Ranch Hand
Posts: 1249
Java Spring Ubuntu
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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....
 
Burkhard Hassel
Ranch Hand
Posts: 1274
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 802
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 602
7
Mac OS X Python
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 802
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 602
7
Mac OS X Python
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Congratulations!
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic