#### Archived

This topic is now archived and is closed to further replies.

# A newbie's dynamic programming example in need of advice if there's any errors

This topic is 5650 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

##### Share on other sites
Question: What keeps your recursion from examining the same node more than once? (i.e. A links to B, B links to C, C links A, etc.)

botman

##### Share on other sites
ohh is it pointers you''ve meant?

##### Share on other sites
No, nothing to do with pointers.

Your algorithm (if I understand it correctly) is this...

1) Start at a point. Loop through all the paths from this point to other points that it connects to.

2) Get the point that is connected to by the shortest path from step 1, if this point is not the destination, call Step 1 with this point.

If you have the following graph...

A -> B (distance = 10)
A -> D (distance = 20)
A -> E (distance = 30)
B -> C (distance = 10)
B -> E (distance = 20)
C -> A (distance = 10)
C -> F (distance = 30)
D -> F (distance = 10)
E -> C (distance = 20)
E -> F (distance = 20)

...and your task was to go from A to F, you would never get there because you would do this...

1. Find the shortest path from A to somewhere else, well, that''s B.
2. Find the shortest path from B to somewhere else, well, that''s C.
3. Find the shortest path from C to somewhere else, well, that''s A.
4. Find the shortest path from A to somewhere else, well, that''s B.
5. (see step 2).

You just get into an endless loop because you don''t keep track of where you''ve been.

botman

##### Share on other sites
Oops... forgot to mention that it is based on the assumption that nodes only move from starting point to the ending point(ie. (C -> A) is not an element of the relation).

I understand that it sounds pretty strange to pros, but it tries not to be too complicated.

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 14
• 30
• 13
• 11
• 11
• ### Forum Statistics

• Total Topics
631781
• Total Posts
3002316
×