[그래프] 플로이드-워셜

✔ 플로이드-워셜

플로이드-워셜란?

• 그래프에서 모든 노드 간에 최단 거리를 구하는 알고리즘
• 음수 가중치 엣지가 있어도 수행할 수 있음
• 동적 계획법의 원리를 이용해 알고리즘에 접근
• A 노드에서 B 노드까지 최단 경로를 구했다고 가정했을 때
  최단 경로 위에 K 노드가 존재한다면 그것을 이루는 부분도 최단 경로라는 원리를 이용
• V는 노드 수, E는 엣지 수일때, 시간 복잡도는 O(V³)
• 모든 노드 간의 최단 거리를 확인해 주기 때문에 시간 복잡도가 빠르지 않으므로 노드의 개수의 범위가 다른 그래프보다 적음

플로이드-워셜 과정

1. 최단 거리 배열을 인접 행렬로 표현
2. s와 e 값이 같은 칸은 0, 다른 칸은 ∞로 초기화
3. 출발 노드는 s, 도착 노드는 e, 이 엣지의 가중치는 w라고 했을 때 D[s][e] = w로 엣지의 정보를 배열에 입력
4. 3중 for문의 형태로 반복하면서 배열의 값을 업데이트

for 경유지 K에 관해 (1 ~ N)
    for 출발 노드 S에 관해 (1 ~ N)
        for 도착 노드 E에 관해 (1 ~ N)
            D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

 

Do it! 알고리즘 코딩테스트 with JAVA

https://inf.run/w9Tn