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

  • 1
    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 clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.