0
음의 가중치 사이클이 그래프에있을 때 최소 거리를 찾는 방법이 없다는 것을 알고 있습니다. 최소 거리의 의미는 없습니다. 플로이드 Warshall 알고리즘 음수 순환 사이클을 가진 그래프를 먹이면 내 질문은 어떻게됩니까? O (n)에서 무한정 실행되거나 종료 될 수 있습니까?음의 가중치 사이클에서 Floyd Warshall 알고리즘의 시간 복잡도
A
답변
1
찾을 수 있듯이 Wikipedia
현재 무게 또는 최대 무게를 기반으로하는 Floyd-Warshall 알고리즘에는 조건이 없습니다.
알고리즘은 모든 정점 쌍을 통과하고 거리를 계산합니다. 대답은 아니오입니다. 무기한으로 실행되지 않습니다.
확실히 알고리즘은 잘못된 대답을 반환합니다 (음수 사이클의 정점에 대해서는 음수 거리가 있음). 예를 들어 정점에서 자체까지의 거리가 음수 일 수 있습니다.
또한이 알고리즘은 부정 사이클 검출에도 사용할 수 있습니다.