Optimization of movement on board

Question

Suppose you have a n x n gaming board and you have a character that can move like a knight on a chess board except he can't move up or left. And each block he moves to has a value which can be accumulated to his points. The player is trying to maximize points and reach T

I came up with a solution but im wondering where it could fail and its run time.

My idea was to create a directed weighted graph (points as weights) to each possible destination and run Dijkstra's algorithm on the graph, however instead of shortest path, we try and find the longest path.

I am guessing the run-time would be O (some thing + |E|+|V|log||V|)

Im not sure what something is.

Answer 1

Dijkstra is not good for finding maximum path. In ordrer to find the maximum path you should multiply each edge weight by -1 and it is well known that dijkstra does not operate correctly on graph with negative weight edges. Instead you will need to use Bellman-Ford algorithm. The complexity will then be O(| V | · | E |) as stated in the wikipedia article.