플로이드-워셜 알고리즘

플로이드-워셜 알고리즘
분류 (가중 그래프에서) 전체-쌍 최단 경로 문제
자료 구조 그래프
최악 시간복잡도
최선 시간복잡도
평균 시간복잡도
공간복잡도

컴퓨터 과학에서, 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 변의 가중치가 음이거나 양인 (음수 사이클은 없는) 가중 그래프에서 최단 경로들을 찾는 알고리즘이다.[1][2] 알고리즘을 한 번 수행하면 모든 꼭짓점 쌍 간의 최단 경로의 길이(가중치의 합)을 찾는다. 알고리즘 자체는 경로를 반환하지는 않지만, 알고리즘을 약간만 변형시키면 경로를 찾을 수 있다.이 알고리즘의 일부 버전은 관계 추이적 폐포를 찾거나, 가중 그래프의 모든 꼭짓점 쌍 간의 최대 폭 경로를 (슐츠 선거 제도와 결합해서) 찾는 것이 가능하다.

En otros idiomas