Ad:

Pascal and Delphi Discussion Thread
Unsolved
Views: 1846

Feb 22nd, 2009

A Nice Shortest path problem !

Expand Post »

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.

thrasas

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

4 posts
since Feb 2009

Permalink

Feb 23rd, 2009

Re: A Nice Shortest path problem !

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?

jsosnowski

Reputation Points: 11

Solved Threads: 11

Junior Poster in Training

Offline

68 posts
since Nov 2007

Permalink

Feb 23rd, 2009

Re: A Nice Shortest path problem !

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 :

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

thrasas

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

4 posts
since Feb 2009

Permalink

Feb 24th, 2009

Re: A Nice Shortest path problem !

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

LizR

Reputation Points: 196

Solved Threads: 190

Posting Virtuoso

Offline

1,735 posts
since Aug 2008

Permalink

Feb 24th, 2009

Re: A Nice Shortest path problem !

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

thrasas

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

4 posts
since Feb 2009

Permalink

Feb 24th, 2009

Re: A Nice Shortest path problem !

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.

LizR

Reputation Points: 196

Solved Threads: 190

Posting Virtuoso

Offline

1,735 posts
since Aug 2008

Permalink

Feb 24th, 2009

Re: A Nice Shortest path problem !

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???

jsosnowski

Reputation Points: 11

Solved Threads: 11

Junior Poster in Training

Offline

68 posts
since Nov 2007

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in Pascal and Delphi Forum Timeline: Declaring a Record Type using Case.

Next Thread in Pascal and Delphi Forum Timeline: Decimal to Binary or hex

DaniWeb Message

Cancel Changes

User Name
Password