计算两点间最短路径

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (24)

0绿瓦-允许玩家移动的自由路径。

通过调用:

 array[x][y]

我想创建最快的算法,以找出最短的路径(如果有一个)之间的地图两点。你会如何处理这个问题?我知道这是个常见的问题。

在这个位置(1,7)的玩家用一些AI发射一颗子弹,在这个位置(6,0)向敌人的玩家射击。子弹必须计算出两名球员之间最短的路线,如果没有,子弹就会撞到墙上爆炸。

问题

如何有效地找到两点之间的最短路径?

提问于
用户回答回答于

这是一个普通的图论问题算法

在图论中,最短路径问题是求图中两个顶点(或节点)之间的一条路径,从而使其组成边的权重之和最小化的问题。

图的顶点对应于交叉口,边对应于路段,每一条以路段的长度加权,图的两个交叉口之间的最短路径的求取问题可以用图中最短路径问题的一个特例来模拟。

暂时存在很多实现这个算法。更简单的实现是Dijkstra算法在最坏的情况下表现为O(|E|+|V|log|V|)何地

v型的数目节点

e的数目边

算法工作说明

Dijkstra最短路径算法的定义

  • 初始节点-我们开始的节点。
  • 节点Y距离-距离初始节点Y型...

算法将分配一些初始距离值,并尝试逐步改进:

  1. 为每个节点分配一个暂定距离值:将其设置为0初始节点以及所有其他节点的∞。
  2. 设置初始节点和现在一样。标记所有其他节点未探视...。创建一组未探视节点称为unvisited set...
  3. 对于当前节点,请考虑它的所有未探视并计算出它们的暂定距离。将新计算的暂定距离与当前赋值进行比较,并分配较小的值。
  4. 当我们考虑完当前节点的所有邻居时,将当前节点标记为已访问的节点,并将其从unvisited set。访问的节点将永远不会再被检查。
  5. 如果目标节点已被标记为已被访问(在规划两个特定节点之间的路由时),或者如果在unvisited set是∞(当计划一个完整的遍历时,当初始节点和未访问的节点之间没有连接时发生),然后停止。算法已经完成...
  6. 否则,选择未探视标记为最小暂定距离的节点,将其设置为新的“当前节点”,然后返回到步骤3。
用户回答回答于

虽然Dijkstra算法确实有效,但在您的例子中,图是一个未加权的图,所以一个简单的BFS就足够了。

伪码:

queue = [startingposition]
prev = [-1, -1, -1 ...] (array of n elements, all -1)
while (queue not empty) 
   u <- pop(queue)
   if u = targetposition then DONE! trace the *prev* array for path
   for (v in every unvisited points adjacent to u):
      prev[v] = u
      push v to queue
   end for
end while

扫码关注云+社区