코테/알고리즘
플로이드-워셜
imname1am
2023. 6. 26. 23:08
반응형
📍 정의 및 특징
모든 노드 간 최단 경로 탐색
- 음수 가중치 에지가 있어도 수행 가능
- DP 원리 이용 (점화식)
D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])
: A → B까지 최단 경로를 구할 때, 최단 경로 위에 K가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로
- 노드 개수의 범위가 적은 경우 사용 (∵ 시간 복잡도가 빠른 편이 아니므로)
- 시간 복잡도 : O(V³)
📍 필요 변수
1. 최단 거리 배열
2. 인접 행렬
📍 실행 과정
- 최단 거리 배열 선언 · 초기화
-D[S][E] = if(S == E) ? 0 : ∞ - 최단 거리 배열에 인접 행렬 사용해 그래프 데이터 저장
- 플로이드-워셜 수행 : 점화식으로 배열 업데이트 → 3중 for문
➕ 예제
[백준/JAVA] 1389번: 케빈 베이컨의 6단계 법칙
🔺 문제 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B
bono039.tistory.com
[백준/JAVA] 11403번: 경로 찾기
🔺 문제 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 🔺 코드 1 2 3 4
bono039.tistory.com
[백준/JAVA] 11404번: 플로이드
🔺 문제 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버
bono039.tistory.com
(참고)
Do it 알고리즘 코딩 테스트 자바편
알고리즘 - 플로이드-워셜(Floyd-Warshall) 알고리즘
컴퓨터/IT/알고리즘 정리 블로그
chanhuiseok.github.io
반응형