Archived

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

savagerx

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

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.)

botman

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.

botman

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