•

Check out our Community Blogs

Register and join over 40,000 other developers!

### Recent Blog Entries

• phi

I love this community !

• JackJames

hi i am jack i am seo expert jack james would love you to read new post

# best algorithm for given problem

shortest path

### #1 artartart

artartart

CC Lurker

• Just Joined
• 1 posts

Posted 14 May 2008 - 06:39 AM

In the plane with integer coordinates, there are X start points and Y endpoints (X=Y). There are also some obstacles in the plane (unwalkable points). The task is to find path from each X to exactly one Y (each Y can be endpoint for exactly one X) such as the sum of all paths ar minimized.

The size of plane is 10^6 x 10^6, max number of start points is 20. There may be 200 rectangular obstacles. Time limit is 10 seconds, memory limit 4GB

I'm considering using A* algorithm to compute shortest paths from each X to each Y, but I'm afraid that it wont be sufficient couse 20x20 times use of A* could be a bit time consuming.

Maybe there is some better algorithm for finding paths from each X to each Y?

Edited by artartart, 14 May 2008 - 06:56 AM.

• 0

### #2 WingedPanther73

WingedPanther73

A spammer's worst nightmare

• Moderator
• 17757 posts
• Location:Upstate, South Carolina
• Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
• Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 14 May 2008 - 07:53 AM

You may want to find the closest Y for each X. If there are any conflicts, find the first and second closest Y for each X, look for a non-conflict mix. Repeat as necessary.
• 0

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/

### Also tagged with one or more of these keywords: shortest path

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download