关于应用于CCHESS的算法的困惑

Question

我意识到必须应用Dijkstra算法才能得到答案的事实。整个算法在answers之一中进行了深入解释。 但是为什么我们需要将Dijkstra的算法应用于这个问题。根据我的知识，Dijkstra会找到最短的距离路径。

但是问题制定者已经明确要求最低成本路径。考虑到这个问题，我们将Prim的算法应用于问题并找到整个棋盘的MST。

Here是问题的链接。

Answer 1

Dijkstra的算法确实用于找到最短距离路径。但是，请注意，“距离”不一定意味着以正常方式测量的距离（即使用标尺）。实际上，Dijkstra算法也可用于在任何网络中查找最短成本路径（假定所有成本大于或等于零）。您所需要做的就是将任意两个节点之间的距离定义为等于相应边的成本。

因此，在这个问题中，当他们搜索最短路径时，他们根据问题中定义的成本函数定义距离。