Pascal and Delphi

A Nice Shortest path problem !

Please support our Pascal and Delphi advertiser: Programming Forums - DaniWeb Sister Site

•

Join Date: Feb 2009

Posts: 4

Reputation: thrasas is an unknown quantity at this point

Solved Threads: 0

thrasas

Offline

Newbie Poster

A Nice Shortest path problem !

Feb 22nd, 2009

Hello everyone! i found some days ago a really nice algorithmic problem, and i am trying to solve it (implement it in pascal in the end).
I know it is a shortest path problem, (it is obvious) but i still can't seem to find any proper approach to it!
Any help (thoughts..) will be appreciated!

So here is the problem:
We have a mail man that is trying to deliver mails to some ports between his home and his office.
The home of the mail man, is at the point (0,0) (cartesian coordinates), and the office at the point (A,B).
In between there are the ports with coordinates X,Y.

The mail man though can do only 2 routes. One in the morning, from home to office and one in the evening from office to home. He must deliver all mails in those 2 routes.
Yet, in the morning route, he can visit only the ports which have a greater x-coordinate than his previous location, and in the evening route he can visit ports with smaller x-coordinate than his previous location.

We should make a program that calculates the minimum distance he must travel, to deliver mails to all the ports.

Input File:
First line contains an integer N, 0<N<=200, the numbers of the port.
second line contains two integers A,B , 1<=A,B<=1000 , the coordinates of the office.
The following N lines contain, the coordinates of the ports X,Y , 1<X<=A and -1000<=Y<=1000.
All coordinates are seperated with space.

OUtput: An integer, the minimun distance.

Please request clarifications if needed.

•

Join Date: Nov 2007

Posts: 68

Reputation: jsosnowski is an unknown quantity at this point

Solved Threads: 11

jsosnowski jsosnowski is offline

Offline

Junior Poster in Training

Re: A Nice Shortest path problem !

Feb 23rd, 2009

To save LizR the effort let me ask you:

What have got thus far? Have you developed any parts of the algorithm such as how to read the file, how to store the data for use, or how to determine the distances?

•

Join Date: Feb 2009

Posts: 4

Reputation: thrasas is an unknown quantity at this point

Solved Threads: 0

thrasas

Offline

Newbie Poster

Re: A Nice Shortest path problem !

Feb 23rd, 2009

yes i have developed all of those! actually in two versions. one suitable to graph algorithms, and one simpler.

Here is the code for the simpler one :

 Help with Code Tags 
 Pascal and Delphi Syntax (Toggle Plain Text) 
 
uses
  SysUtils;
 
type
coordinates = record
  X:integer;
  Y:integer;
end;
 
var
space:char;
N,
i,j,prev1,prev2:integer;
input,
output:text;
port:array[1..202] of coordinates;
d:array [1..7,1..7] of real;
temp:coordinates;
 
 
 
begin
 
  {Input data}
  assign(input,'C:/evripos.in')  ; {file named evripos}
  reset(input);
  readln(input,N);
  readln(input,port[N+2].X,space,port[N+2].Y);
  for i := 2 to N+1 do
    readln(input,port[i].X,space,port[i].Y);
  close(input);
  port[1].X:=0;
  port[1].Y:=0;
 
  (*------------------------------------------------*)
 
  (* sort coords from 0 to A*)
    for i := 2 to N+2 do
      for j := N+2 downto i do
        if port[j].X < port[j-1].X then
          begin
            temp:=port[j];
            port[j]:=port[j-1];
            port[j-1]:=temp;
          end;
 
  (*create distance matrix*) {it is also an adjacency matrix if considered as a graph}
  for i := 1 to 7 do
    for j := 1 to 7 do
      d[i,j]:= sqrt(sqr(port[i].X-port[j].X)+ sqr(port[i].Y-port[j].Y));
uses
  SysUtils;

type
coordinates = record
  X:integer;
  Y:integer;
end;

var
space:char;
N,
i,j,prev1,prev2:integer;
input,
output:text;
port:array[1..202] of coordinates;
d:array [1..7,1..7] of real;
temp:coordinates;



begin

  {Input data}
  assign(input,'C:/evripos.in')  ; {file named evripos}
  reset(input);
  readln(input,N);
  readln(input,port[N+2].X,space,port[N+2].Y);
  for i := 2 to N+1 do
    readln(input,port[i].X,space,port[i].Y);
  close(input);
  port[1].X:=0;
  port[1].Y:=0;

  (*------------------------------------------------*)

  (* sort coords from 0 to A*)
    for i := 2 to N+2 do
      for j := N+2 downto i do
        if port[j].X < port[j-1].X then
          begin
            temp:=port[j];
            port[j]:=port[j-1];
            port[j-1]:=temp;
          end;

  (*create distance matrix*) {it is also an adjacency matrix if considered as a graph}
  for i := 1 to 7 do
    for j := 1 to 7 do
      d[i,j]:= sqrt(sqr(port[i].X-port[j].X)+ sqr(port[i].Y-port[j].Y));

•

Join Date: Aug 2008

Posts: 1,735

Reputation: LizR has a spectacular aura about

Solved Threads: 186

LizR

Offline

Posting Virtuoso

Re: A Nice Shortest path problem !

Feb 24th, 2009

So. Whats your specific problem? You've told us the homework question, you have some code.. What problem specifically are you having?

Did I just hear "You gotta help us, Doc. We've tried nothin' and we're all out of ideas" ? Is this you? Dont let this be you! I will put in as much effort as you seem to.

•

Join Date: Feb 2009

Posts: 4

Reputation: thrasas is an unknown quantity at this point

Solved Threads: 0

thrasas

Offline

Newbie Poster

Re: A Nice Shortest path problem !

Feb 24th, 2009

my "problem" is that i don't seem to understand what shortest path is needed!

I have tried Dijkstra's algorithm but it doesn't seem to work well for this case, because we have 2 routes....

Yet, now i am working on a greedy algorithm to find all possiple paths and take the smallest... but that would be O(n!) worst case.. and that's not really good...

•

Join Date: Aug 2008

Posts: 1,735

Reputation: LizR has a spectacular aura about

Solved Threads: 186

LizR

Offline

Posting Virtuoso

Re: A Nice Shortest path problem !

Feb 24th, 2009

As its your homework, why not ask your professor? If you havent followed the question any advice we give you could be wrong on the grounds it could be the teacher has felt they explained and we might say something in contradiction.

Did I just hear "You gotta help us, Doc. We've tried nothin' and we're all out of ideas" ? Is this you? Dont let this be you! I will put in as much effort as you seem to.

•

Join Date: Nov 2007

Posts: 68

Reputation: jsosnowski is an unknown quantity at this point

Solved Threads: 11

jsosnowski jsosnowski is offline

Offline

Junior Poster in Training

Re: A Nice Shortest path problem !

Feb 24th, 2009

Your problem here is clearly the algorithm, not the coding. Do you actually need Dijkstra's algorithm?

If you take all the points and determine the average Y value and then split the list of points in two using the middle 'y' as the division line. Now for each group sort them by x values andyou will have the sequence order. Both groups have to traverse the same X distance and the Y distance is less than if you cross the center 'y' line. Correct???