2017-12-27 467 views
1

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

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

Here是问题的链接。

回答

0

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

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

+0

您能否请您解释一下“实际上,Dijkstra的算法也适用于在任何网络中查找最短成本路径(假设所有成本大于或等于零)”。据我所知,最短路径和最低成本路径绝不相同。 –

+0

如果我们将两个节点之间的“距离”定义为获取边缘的成本,那么路径的“距离”只是说明路径成本的另一种方式。换句话说,我们使用“距离”作为成本的同义词。 –