Dijkstra算法，对于某些节点（不是两个，不是整个图）的最短路径只运行一次

Question

因此，dijkstra算法是（最佳的）用于搜索加权（无负）连通图的最短路径的算法。Dijkstra算法可用于寻找两点/顶点的最短路径。它可以用来寻找所有顶点的最短路径。

问题：我的理解正确吗？它还可以用于查找某些顶点对的最短路径吗？例如，图有A，B，C，D，E，F，G，H，I，J，K，我们只对A，B的最短路径感兴趣；C、 K.我们可能只转动算法一次就找到两条路径吗？

Answer 1

首先，Dijkstra不是最好的算法，许多启发式算法在大多数实际实现中都优于它。

我们只对A，B的最短路径感兴趣；C、 K

看起来你可以看一看*算法，它消除了那些不会以最低成本将你带到最终目的地的节点。但它需要对各个节点到目的地的距离进行良好的估计（因此也需要“启发式”一词）。

至于你的主要问题，答案是肯定和否定的，还有一些间接费用。我们都知道，每当一个节点从min堆中移除时，算法就完成了。

因此，一旦您的节点从最小堆中移除，就终止它，但这并不意味着它只找到给定对的最短距离。在目标节点之前从最小堆中移除的所有节点也是它找到最短路径的节点。

另外，您的目标节点可能是从最小堆中删除的最后一个节点，这基本上意味着您已经计算了从源到所有节点的最短路径。

Answer 2

你需要跑两个迪克斯特拉。一个从A开始，另一个从C开始。

您可以做的是从{A， C}（一组Dijkstra）运行它，直到您找到了通往B和K的路径。但这并不能保证生成的路径实际上是从A到B和C到K，它也可能是C，B和C，K .实际上，所有{A， C}， B和{A， C}， K的组合都是可能的。

最好的

一点也不。这是一个很好的概念，大量用于许多其他类似的算法。有许多变体，如A*、Arc-Flags等。但是原始的Dijkstra是超级慢，因为它同样在各个方向搜索。

想象一个查询，您在其中模拟了整个世界。您的目的地距离1小时。然后，Dijkstra将找到在1小时内可以到达的所有节点的最短路径。所以它也会考虑到你的邻国进行短暂的飞行，即使这是完全错误的方向。算法A*是Dijkstra的一个简单修改，它试图通过引入一个启发式函数来改进该算法，该函数能够（希望）很好地猜测最短路径距离。通过这种方式，你的Dijkstra获得了方向感，并尝试首先优先搜索目的地的方向。

一个简单的启发式方法是像乌鸦一样飞翔。请注意，这种启发式方法在道路网络上表现不佳，在公交网络上表现尤其糟糕（你通常需要驾驶10分钟进入错误的方向才能上一条让你最终提前到达的高速公路，或者你需要先驱车到某个大城市才能获得一辆好的快车）。其他启发式算法涉及计算地标，它们产生相当好的结果，但需要大量的预计算和空间（通常不是问题）。