假设你有一个n x n游戏板，你有一个角色可以像棋盘上的骑士一样移动，除非他不能向上或向左移动他移动到的每个街区都有一个可以累加到他的点数的值。玩家试图最大化点并达到T。
我想出了一个解决方案，但我想知道它在哪里可能失败，它的运行时间。
我的想法是创建一个指向每个可能的目的地的有向加权图（点作为权重），并在图上运行dijkstra的算法，然而，不是最短路径，而是
试着找到最长的路。
我猜运行时是O（一些东西+| E |+| V | log | V |）
我不知道是什么东西。
最佳答案
Dijkstra不善于寻找最大路径。在OrdRR中寻找最大路径，你应该将每个边权乘以-1，并且众所周知，Dijkstra在负权重边的图上不能正确操作。相反，您需要使用Bellman-Ford algorithm。复杂性将如维基百科文章中所说的O(| V | · | E |)。
关于algorithm - 优化机上运动，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/21807240/