Floyd Warshall

[APSP] Floyd Warshall 알고리즘

• Algorithm
• 2021년 4월 12일

벨만-포드 알고리즘과 다익스트라 알고리즘과 달리 모든 최단 경로를 구하는 알고리즘이다. (물론 두 알고리즘도 모든 정점에대해 수행하면 모든 최단 경로를 구할 수 있다.) 1. 특징 음의 가중치 허용 optimal substructure 개념 이용 배열을 이용하여 구현 밀집그래프에서 모든 edge간 경로 구할때 적합 2. Pesudo Code 3. 구현 방법 그래프 edge가 주어졌을때, edge들의 정보를 이용하여 각 edge간 거리 정보를 저장할 distance 2차원 행렬과 경로를 구하기 위해 이전 노드를 저장할 previous 2차원 행렬 생성 distance 행렬은 Infinity로 previous 행렬은 NIL(-1)로 초기화 그래프 G의 edge들의 가중치의 정보를 이용해 distance행렬을 초기화하고 자기의 거리는 0으로 초기화 3중 반복문을 이용하여, 현재까지 계산된 i - j까지의 경로 값보다 사이에 k를 경유하는 경로 값이 더 작다면 값을 바꾸기 4. 시간복잡도 매번 모든 노드들의 조합에 대해서 현재까지의 최단 경로를 구하고 총 |V-1| 번 반복하기 때문에 O(|V|^3) 의 시간복잡도를 갖는다....