CCHESS에 적용 할 알고리즘에 대한 혼란

Question

저는 Dijkstra의 알고리즘을 적용하여 답을 얻어야한다는 사실을 알고 있습니다. 전체 알고리즘은 answers 중 하나로 깊이 설명되어 있습니다. 그러나 왜 우리는이 문제에 Dijkstra의 알고리즘을 적용해야합니까? 내 지식에 따라 Dijkstra는 최단 거리 경로를 찾습니다.

그러나 문제 설정자는 최소 비용 경로를 분명히 요구했습니다.이 질문에 Prim의 알고리즘을 적용하고 전체 체스 보드에 대한 MST를 찾아서는 안됩니다.

Here이 문제의 링크입니다.

Answer 1

Dijkstra의 알고리즘은 실제로 최단 거리 경로를 찾는 데 사용됩니다. 그러나 "거리"는 정상적인 방법으로 측정 된 거리 (즉, 눈금자)를 의미하지 않아야합니다.

실제로 Dijkstra의 알고리즘은 모든 네트워크에서 가장 짧은 비용 경로를 찾는 데 효과적입니다 (모든 비용이 0보다 크거나 같음). 두 노드 사이의 거리를 해당 가장자리의 비용과 같도록 정의하기 만하면됩니다.

따라서이 문제에서 최단 경로를 검색 할 때 문제에서 정의 된 비용 함수 측면에서 거리를 정의합니다.