CODEWITHSUNDEEP
algorithmgraphgraph-algorithm
XogoX
XogoX

Reputation: 149

Find a shortest path with some conditions

Let me introduce the problem :

You have a QR code (the QR code is always a square in this problem) like this one.
one http://img11.hostingpics.net/pics/514457code.png
You can start anywhere in the top of the QR code (so anywhere in the first line) and you have to find a path to reach a case anywhere in the bottom line (so anywhere in the last line).

You have to minimize the number of black cases in the path, and if you have several paths with the same number of black cases, you have to find the shortest one.

Example of solution :

Find an algorithm to find the shortest path with those conditions.

My Solution

First, I consider the problem as a directed grid graph, where each pixel is a vertex, and each vertex has as many edges as neighbors.

So for example, the vertex at the top left can reach its right neighbor and its bottom neighbor.

I attribute the weight of the edge as follow :

A small value (<<1) is here to find the shortest path in the case where we have several paths with the same number of black cases.

So with this representation, let V be the number of vertices, W the number of vertices in a line and E the number of edges, we have E = W(W-1)*2*2.

Then I create 2 subsets : the first one contains all the possible starting vertex (first line of the QR code, so W vertices) and another one with the possible final destination(last line and so W vertices).

I use Dijkstra to compute the shortest path in O(V lg(V)) (with the library I use) and I do it W times for all the starting nodes and I look for the shortest path to each destination vertex.

So I find the shortest path in O(V*W lg(V)) = O(V^3/2 Lg(V)).

Question

Do you have a better solution to this problem ? With a grid graph representation or whatever ?

Upvotes: 2

Views: 1419

Answers (1)

kraskevich
kraskevich

Reputation: 18576

Here is a faster solution:

  1. Let's find paths that contain the smallest number of black cells. We can use 0-1 breadth-first search. An edge that leads to a white cell should have a weight 0 and an edge that leads to a black cell should have a weight 1. There is no need to run it from each of the vertices in the top row separately: we can add them all to the queue in the beginning and then run a breadth-first search only once(we should not forget to add all white cells from the first line before the black ones).

  2. Let's call a directed edge from u to v good if dist[v] == dist[u] + weight(u, v). Now we can run a simple breadth first search(again, from all cells of the top row in a batch) on a graph that contains only "good" edges(this time all edges have weight 1).

  3. Now we can just choose the best cell from the last row.

This solution requires O(V) time(its just two breadth-first searches) and it always produces an optimal answer(no small magic numbers are required).

Upvotes: 1

Related Questions