Jump to content
  • Advertisement


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.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Dear pros, I am not pushing all the debugging work to you guys but it''s just that this piece of code took me three days to get the solution(I know I''m slow). And now that I''ve just completed, I believe I''ll be able to get more errors spotted if I''ve asked for your professional help and guidance. Thanks =) I''ve just written this piece of code which I hope could get some feedback on errors from the pros here.... purpose: To find the shortest route, distance to be travelled in a directed graph. data dictionary: Node defines a Record location isoftype Num//numeric representation linkage isoftype ptr toa Link_Node endRecord Link_Node defines a Record distance isoftype Num p isoftype ptr toa Node next isoftype ptr toa Link_Node endRecord DESTINATION is a Num constant which denotes the ending point. "^" denotes pointer dereference "." same as in C++ "in [ARG]" denotes read-only/local parameter function Calculate_Distance returnsa Num(arg isoftype in ptr toa Link_Node) //purpose: to get a link,calculate & return min. if(arg^.p^.location = DESTINATION) then return arg^.distance else return distance + Min(arg^.p) print("go ", arg^.p^.location) endif endfunction procedure Get_Min(ln isoftype in ptr toa Link_Node,min isoftype out Num) shortest, temp isoftype Num shortest <- 99999//assume longest distance loop exit when (ln = nil) temp <- Calculate_Distance(ln) if(temp < shortest) then shortest <- temp endif ln <- ln^.next endloop min <- shortest endprocedure procedure Min(arg isoftype in ptr toa Node,min isoftype out Num) Get_Min(arg^.linkage,min) endprocedure The road may be long, wind may be rough. But with a will at heart, all shall begone. ~savage chant

Share this post

Link to post
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.)


Share this post

Link to post
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.


Share this post

Link to post
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.

Share this post

Link to post
Share on other sites

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!