關於應用於CCHESS的算法的困惑

Question

我意識到必須應用Dijkstra算法才能得到答案的事實。整個算法在answers之一中進行了深入解釋。 但是爲什麼我們需要將Dijkstra的算法應用於這個問題。根據我的知識，Dijkstra會找到最短的距離路徑。

但是問題制定者已經明確要求最低成本路徑。考慮到這個問題，我們將Prim的算法應用於問題並找到整個棋盤的MST。

Here是問題的鏈接。

Answer 1

Dijkstra的算法確實用於找到最短距離路徑。但是，請注意，「距離」不一定意味着以正常方式測量的距離（即使用標尺）。實際上，Dijkstra算法也可用於在任何網絡中查找最短成本路徑（假定所有成本大於或等於零）。您所需要做的就是將任意兩個節點之間的距離定義爲等於相應邊的成本。

因此，在這個問題中，當他們搜索最短路徑時，他們根據問題中定義的成本函數定義距離。