我需要生成最短路线。适合我要求的第一个解决方案是 Dijkstra 算法，因此我实现了相同的算法(Java)。后来，我不得不修改实现以生成“转弯次数最少”的最短路线。经过一番摸索之后，我想出了一个解决方案，尽管在现有的 Dijkstra 算法实现中添加了很多条件。现在我的问题是，有没有更好的方法来解决这个问题(比如，任何现有的算法已经这样做了)？我的解决方案包括在路线计算迭代中的每个节点中存储额外的转弯信息，并在回溯路线时使用这些信息。
最佳答案
您不需要对 Dijkstra 进行任何回溯或实质性调整。只需为每个节点跟踪(如您所做的那样)当前到该节点的最短路径上的最少转弯次数。每当您松弛一条边时，如果生成的路径与当前最短路线一样短，您就会选择转弯次数最少的一条。
编辑:正如评论中所指出的，这种方法忽略了这样一个事实，即所选路线的传入边缘的方向会影响后续路径的转弯数。这将通过在每个节点中存储最短距离+转弯每个传入边或每个唯一传入角度(无论您如何测量)来解决。
或者，为了减少对 Dijkstra 的修改，您可以预先修改图形:将每个节点拆分为每个传入边的一个节点(以便每个生成的节点只有一个原始节点的传入边)，但是复制所有传出边，以便每个结果节点都具有原始节点的所有传出边(每个传出边都必须指向边另一端节点的适当副本)。您可能会看到一些生成的节点有多个传入边，但在这种情况下，这些边另一端的节点都是同一原始节点的副本，因此代表“相同”的原始边 - 因此，每个传出边缘可以明确地标记为该边缘是否表示该节点的转出(相对于节点的传入边缘)。请注意，原始图中的最佳路径将仍然存在于新图中(并且不会引入更好的路径)。现在，只需修改 Dijkstra 即可跟踪与每个节点的最短路径相关联的转弯数。每当从 u 到 v 的边松弛并且候选路径与您之前为 v 找到的最短路径一样短时，比较 < em>u 的回合数加上边的回合数(0 或 1，取决于边是否构成一个回合)到 v 的回合数，并将其用作决胜局。
关于java - 转弯最少的最短路线，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35168676/