CODEWITHSUNDEEP
c++algorithmmatrixpathshortest-path
Sergio Checo Nuñez
Sergio Checo Nuñez

Reputation: 21

Shortest path weighted matrix

Find the shortest path from any element on the leftmost side of a given n x n matrix to any element on the rightmost side of the matrix.

Movement: Movement can only be one square at a time. You may move left,right, up-left, up-right, down-left, and down-right.

Weight: The cost to move from X element to Y on the matrix is |Y - X|

Runtime: Devised Algorithm must be at most O(n2)

Example:

Example

Tried so Far:

Tried so far

Problem with this solution.

Runtime is O(n2 Log n2) which is slower than O(n2).

Upvotes: 0

Views: 1465

Answers (1)

Bastian J
Bastian J

Reputation: 372

You can exploit that when you consider the edges in your graph directed, your graph is acyclic and this has a (partial) topological order. In this case, you can just compute the distance from the left for each node from-left-to-right, i.e. column bei column.

In the first column, this distance is 0 for all nodes, i.e. d(Upper left)=0, d(middle left)=0, d(lower left)=0.

In the second (and all following) column(s), you have at most three candidate values to pick the minimum from, e.g d(Upper middle)=MIN[d(Upper left)+4,d(middle left)+2]=2.

That is, computing the values from left to right only takes constant time per node, Theta(n^2) overall. More generally, for N nodes and M edges, this takes O(NM) for a single-source-shortest-path computation.

[Edit: I removed the reference to dynamic programming as it confuses more than ist helps. Added an example.]

Upvotes: 1

Related Questions