A Nice Shortest path problem !

[thrasas]

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.

[jsosnowski]

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?

[thrasas]

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 :

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

[LizR]

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

[thrasas]

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

[LizR]

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.

[jsosnowski]

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