728x90
| 다익스트라 | 벨만-포드 | 플로이드-워셜 | |
| 시작 노드 (시작점) | O | O | X (모든 노드) |
| 음수 간선 | X | O | O |
| 시간 복잡도 | O(ElogV) | O(EV) | O(V³) |
1. 다익스트라
- 출발 노드와 모든 노드 간의 최단 거리 탐색
- 음수간선 X
- S 시작점부터 다른 모든 노드로 가는 최단거리 구하는 알고리즘
- 시간복잡도 : O(ElogV)
- 문제 유형
- 음수간선이 없는데 시작점이 있고 최단거리 구하는 문제
- 원리
- 최단거리를 구할 노드에서 시작하여 거리가 입력된 노드 중 최단거리가 가장 작은 노드를 돌아가며 선택
- 노드를 돌아가면서, 더 거리가 나오면 값 갱신하여 저장
2. 벨만-포드
- 특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색
- 음수간선 OK
- 음수 사이클의 존재 여부를 판단 할 수 있음
- 시간복잡도 : O(EV)
- 문제 유형
- 음수사이클이 있는 지 체크하는 문제 → 시간여행, 과거, 웜홀
- 음수간선, 시작점이 있고 최단거리 구하는 문제
- 원리
- 에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화
- 모든 에지를 확인해 정답 리스트 업데이트
- 음수 사이클 유무 확인 : 모든 에지를 한 번씩 다시 사용해 업데이트 되는 노드가 발생하는지 확인
3. 플로이드-워셜
- 시작점 X
- 모든 노드간에 최단 경로 탐색
- 시간복잡도 O(V³) 안좋음 ➡️ 노드의 개수 100~200까지 사용 가능
- 문제 유형
- 시작점이 없고 모든 도시간의 최단거리, 모든 도시 100개 이하
- 3중 for문
- 원리
- A 노드에서 B 노드까지 최단 경로를 구했다고 가정했을 때, 최단 경로 위에 K노드가 존재한다면 그것을 이루는 부분 경로 역시 최단경로
- 점화식 D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])
728x90