Using Single Source Shortest Path to traverse a chess board

Question

Say we have a n x n chess board (or a matrix in other words) and each square has a weight to it. A piece can move horizontally or vertically, but it can't move diagonally. The cost of each movement will be equal to the difference of the two squares on the chess board. Using an algorithm, I want to find the minimum cost for a single chess piece to move from the square (1,1) to square (n,n) which has a worst-case time complexity in polynomial time.

Could dikstras algorithm be used to solve this? Would my algorithm below be able to solve this problem? Diijkstras can already be ran in polynomial time, but what makes it this time complexity?

Pseudocode:

We have some empty set S, some integer V, and input a unweighted graph. After that we complete a adjacency matrix showing the cost of an edge without the infinity weighted vertices and while the matrix hasn't picked all the vertices we find a vertex and if the square value is less then the square we're currently on, move to that square and update V with the difference between the two squares and update S marking each vertices thats been visited. We do this process until there are no more vertices.

Thanks.

Could dikstras algorithm be used to solve this? assuming that the differences are taken in absolute value, then yes — sve
@svs But if I wanted it in polynomial time would I have to used an undirected or directed implementation? — Tyler
@svs I know this is kind of a hard thing to implement, but what would make an algorithm like this have a time complexity of polynomial time? — Tyler
algorithm like this if you talk about your algorithm I'm having a difficult time to understand it . Dijkstra would be enough. You can also use dynamic programming to solve your problem. The complexity is O(MN) where MxN is the size of your board. — sve

Richard Richard · Accepted Answer · 2015-10-13T22:15:10

Since you are trying to find a minimum cost path, you can use Dijkstra's for this. Since Dijkstra is O(|E| + |V|log|V|) in the worst case, where E is the number of edges and V is the number of verticies in the graph, this satisfies your polynomial time complexity requirement.

However, if your algorithm considers only costs associated with the beginning and end square of a move, and not the intermediate nodes, then you must connect all possible beginning and end squares together so that you can take "short-cuts" around the intermediate nodes.

Using Single Source Shortest Path to traverse a chess board

1 Answers