修改了Djikstra的算法

Question

因此，我正在尝试概念化某些东西：

假设我们有一个尺寸N的称重图。A和B是图上的节点。您想找到从A到B的最短路径，给定一些警告：

1. 图上的运动由长度为48的圆周循环调节：

   循环{

        0 <= L <= 24  movement IS possible
   
       25 <= L <= 48 movement IS NOT possible
   

   }

   为了简单起见，我们将此周期称为“时间”。

2. 节点A和B之间的距离等于：

   shout_distance（a至b）-1或shortest_distance（a至b） + 1

   取决于他们的方向

3. 边缘的重量表示在节点之间旅行所需的“时间”。

我想创建一种算法，该算法将为我带来最短的路径，考虑到这些约束，假设一个算法是从节点a（循环）= 12离开节点的。这需要最少的“时间”。

第一步显然是要考虑到影响最短距离的方向（即它们以上述方式定向），这对于Djikstra的算法而言是简单的添加或缩写

我在弄清楚的是如何考虑算法中的周期……这是否很简单，就像一张if语句检查以查看当前周期时间是否在允许移动的约束范围内？

我的想法可行吗？如果没有，我应该以不同的方式提出任何建议吗？

我知道这个问题似乎真的很基本，但是我只是无法围绕它。

Answer 1

我并不是真的了解您的问题描述，但是如果您按时类比，唯一阻止您使用djikstra的算法的事情是某些边缘的负成本（即：某些边缘及时返回）。如果这是问题，您可以使用可以处理负面边缘的替代算法来解决它，例如 贝尔曼福人