2017-12-27 411 views
1

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

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

Here是問題的鏈接。

回答

0

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

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

+0

您能否請您解釋一下「實際上,Dijkstra的算法也適用於在任何網絡中查找最短成本路徑(假設所有成本大於或等於零)」。據我所知,最短路徑和最低成本路徑絕不相同。 –

+0

如果我們將兩個節點之間的「距離」定義爲獲取邊緣的成本,那麼路徑的「距離」只是說明路徑成本的另一種方式。換句話說,我們使用「距離」作爲成本的同義詞。 –