按顺序访问节点找到图中的最短路径

Question

源头是A，节点的顺序是["C", "D", "E"]，必须经过处理才能达到目标。

我通过从 A-C、C-D、D-E 找到最短路径，使用 Dijkstras 算法找到了解决方案。有没有一种优化的方法可以一次找到最短路径。我们可以用 A* 做得更好吗？如果 A* 提高了性能，我们如何定义启发式函数？

这是我的图表。

最短路径：A - B - C - D - C - E 。如果它有助于最短路径，我们可以在这里再次访问节点。

Answer 1

我们可以用 A* 做得更好吗？

号

Dijkstra（注意拼写）是寻找图中两个节点之间最短路径的最佳方法。

A* 在整个图不可用时使用，只有局部环境不可用。当 Dijkstra 可行时，它总是比 Dijkstra 慢。

Answer 2

Dijkstra 算法是寻找图中最短路径的最佳选择。 Dijkstra 算法的时间复杂度为 O(E + VlogV)，其中 E 是边数，V 是图中的节点数。 A* 算法的时间复杂度为 O(E + VlogV)，因此速度较慢。