问我们可以在Dijkstra算法中增加转向惩罚吗？

EN

Dijkstra不能直接包含转向惩罚，因为它是建立在到达节点的成本与其“上下文”无关的假设之上的。

有可能重写你的图，这样每一轮都与取一条边相关联，所以轮成本变成了正常成本。然后，可以将Dijkstra应用于该图。完整的解释可以在“路线规划中的转弯成本建模”(斯蒂芬·温特)中找到。用于此(折线图)的图有时被称为对偶图，尽管该术语传统上具有不同的含义。粗略地说，您为每条原始边引入一个节点，如果相应的边都与相同的原始节点相邻，则在两个新节点之间引入一条边(每两步的微小路径由新图中的一条边表示)。引出源和进入目标的所有边对应于新图中的单独节点，为了避免将问题转变为多源/多目标最短路径，您可以添加额外的源节点和目标节点，这些节点“将边连接在一起”(零成本)。