Win a copy of Re-engineering Legacy Software this week in the Refactoring forum
or Docker in Action in the Cloud/Virtualization forum!

# Graphs and Dijktra's algorithm..

Justin Fox
Ranch Hand
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

Justin

Justin Fox
Ranch Hand
Posts: 802

Burkhard Hassel
Ranch Hand
Posts: 1274
Hi,

did you check this?

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

Bu.

Shaan Shar
Ranch Hand
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....

Burkhard Hassel
Ranch Hand
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
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
Posts: 602
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
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
Posts: 602
7
Congratulations!