1

There is a N * N matrix, for eg., we can take a 3 * 3 matrix,

3 6 5 9
4 5 0 8
8 7 9 0
3 4 0 1

The problem is to traverse all the '0's in the given matrix by passing through minimum numbers. For eg.,if we start from 3 (1,1), we can reach (2,3) by passign through (1,1)--> (1,2)--> (2,3) but we have to take the way (1,1)-->(2,2)--> (2,3).since we have to use minimum weight in the path. (3+6 weight in the first case and 3+5 weight in the second case).

we have design an algorithm to traverse all the 0's with minimum weight in the path.

My algorithm : 1. Mark all the 0's in the given matrix and count. 2. BFS loop: Induce a BFS from any node to reach the 0's. exit loop once the 0's are found.

but the weight of the path should be the minimum to find the 0's, could anyone help me in solving this?

Improve this question
1
  • 2
    Can you move in all directions? or only right and down? If all directions - it's Traveling Salesman Problem. Commented Mar 12, 2015 at 18:03

1 Answer 1

Reset to default
1

This is a variation of the Traveling Salesman Problem, which is NP-Complete (This means there is no known efficient solution, and most believe such a solution does not exist).

Possible solution for small matrix:

  • Represent your matrix as a weighted graph, where a vertex is a cell and an edge is a possible move from two cells, with the weight being the value of the target cell.
  • You can find all-to-all shortest path using Floyd-Warshall algorithm, and create a graph containing only zeros, and the weight to move from each zero to the other, according to Floyd-Warshall weights.
  • Use a TSP solver (a naive one is to generate all permutations and chose the best out of them)

The thread: Find the shortest path between a given source and a set of destinations deals with steps 2+3 in the above explanation with more details.

However, if you have extra restrictions that you did not mention (for example, can only move torwards down and right), your underlying graph is actually a Directed Acyclic Graph, and you can solve it more efficiently.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Thanks a lot, i will read through it. Could you please comment on my solution ?
@vignesh Your solution fails becasue (1) It does not take into account weights. (2) BFS is good only for finding a shortest path to a point, and it does not take the account you need to go through ALL zeros, and will fail to find optimal solution (unless for specific cases)

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.