CODEWITHSUNDEEP
calgorithmgraphbreadth-first-search
kaixi
kaixi

Reputation: 37

Find BFS best path array

Description:

I have a problem very similar to https://leetcode.com/problems/jump-game-ii/description/.

Apart from discovering the minimum steps to reach the end, I need to retrieve the winning path array. The winning path that is needed for my problem must satisfy the rule that given path A like [0,2,4,7] there are not any other paths with the same price (steps to the end, 3 in this case) whose nodes starting from the path's end has lower indexes.

The single step from i to i+1 has not price equal to 1 but is 0 <= x <= 2^32-1.

An example:

This has to work also in reverse:

Note that this rule is applied from right to left.

Clearly, I can produce all the paths with BFS and hence compare them but is there a more efficient way?

Upvotes: 0

Views: 61

Answers (1)

John Bollinger
John Bollinger

Reputation: 181199

The winning path that is needed for my problem must satisfy the rule that given path A like [0,2,4,7] there are not any other paths with the same price (steps to the end, 3 in this case) whose nodes starting from the path's end has lower indexes.

I can produce all the paths with BFS and hence compare them but is there a more efficient way?

Yes.

Search backwards, from end to start, in BFS fashion. When you enqueue each node's unvisited successors, do it in increasing order by index. The first path you discover will then be the reverse of the path you're looking for.

Upvotes: 0

Related Questions