Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The efficient algorithm needs to be done and proved for the best solution for the given problem:

User inputs: (#) Size of the NxN Grid. (N); (#) No. of Paths: Z; (#) Source and Destination Coordinates of each of the individual Z paths.

Given: (#) Each path comprises of the cells which are ADJACENT to each other and NOT diagonal. (#) Time taken to cross each cell is EQUAL and is an unit time. (#) Travelling starts from the respective source coordinates of each path in the grid SIMULTANEOUSLY. (#) Paths may intersect, BUT after say 'x'th unit time no two paths must intersect in one particular cell at a time. If such case arises, then one of the paths need to bypass into a new path taking alternate adjacent cell just before the clashing cell.

Output: Z no. of paths which are SHORTEST possible without clash.

enter image description here

[Say there are two paths (Z=2), say X to Y and W to Z. While travelling, both X and W start simultaneously from their respective source coordinates, going to their respective destinations Y and Z such that they should take the SHORTEST possible path, AND after 'x'th unit time, they must not CLASH (when both the paths have traveled exactly (x-1) no. of cells and clashing into the 'x'th cell) into one single cell. If that happens, one of the path needs to be bypassed towards its destination keeping in mind without clash, shortest possible path. And this has to be implemented for Z no. of lines starting simultaneously in the grid.]

share|improve this question
The problem is not yet well-defined. In general it will be possible for any individual path to be as short as it was without the no-clash constraint. How do you propose to measure "shortest," though, when it applies to multiple paths? Do you want to use the total of all the path lengths? The maximum length? The maximum of the amount of length increases? Or perhaps do you want to give priorities to the different paths? These all are different problems with potentially different solutions. – whuber Jan 13 '13 at 20:40
Thanks for responding. Yes, I should have mentioned it clearly. Yes, I do mean the "total of all the path lengths" must be as less as possible. And, since I'm a new user, I wasn't allowed to use any image then. Kindly check the image so that you can get a better idea about the clash thing as how it is supposed to happen. Thankyou Sir. – Sayon Kumar Saha Jan 15 '13 at 11:29

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.