我目前正在实施一个导航系统，用于通过欧洲进行路由。到目前为止，我已经实现了最短路径（Dijkstra 和 A*）。这是最简单的部分，现在我需要一些最快路径的算法。它必须快速可靠。
我知道这可以通过为道路质量（例如 1 条高速公路、2 条主干道......）分配值来完成，然后将这些值与路线成本相乘，最后使用 Dijkstra 或 A*，但这还不够复杂。
我正在寻找更准确的算法。地图本身包含各种数据，比如道路质量、限速、红绿灯位置等，我想用它。
有什么好的算法吗？或者至少是对 A* 的一个很好的修改？
在最短路径的实现中，您选择距离作为边缘的权重。
现在，如果您想找到最快的路径，您只需选择预期的旅行时间作为边的权重。同样，如果您想要最可靠的路径，您可以选择一些“可靠性”度量作为边缘的权重。
A*（虽然并不总是最优的，因为它依赖于启发式函数）可能是此类应用程序的最佳选择。如果你的 A* 不够准确，我建议你要么选择 Dijkstras，要么花一些时间调整和改进你的启发式函数。
这取决于您所说的“最快”路径是什么意思。如果您知道您可以在道路的每一段上行驶的平均速度，那么您可以转换您的图表，使边缘包含“行驶时间”而不是“距离”。然后你可以在新图上做一个最短路径算法。
不过，您似乎提到这还不够好。我认为问题在于您必须定义“最快”的含义。道路质量如何影响速度？红绿灯呢？这些都是你必须找到一种方法来解释的变量。如果您作为人类不知道您将使用的指标，那么计算机将很难做到这一点。