반응형
☝ 다익스트라 최단 경로 알고리즘
- 그래프에서 여러 개의 노드가 있을 때, 특정 노드에서 다른 노드로 가는 최단 경로를 구하는 알고리즘
- '음의 간선'이 없을 때 정상적으로 동작
- 음의 간선은 0보다 작은 값을 가지는 간선을 의미
- 그리디 알고리즘으로 분류됨
- 다익스트라 최단 경로 알고리즘 원리
- 출발 노드 설정
- 최단 거리 테이블을 초기화
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
- 해당 노드를 거쳐 다른 노드로 가능 비용을 계산해 최단 거리 테이블을 갱신
- 3-4번 과정을 반복
- 간단한 다익스트라 알고리즘의 시간 복잡도 👉 O(V²) (V는 노드의 개수)
- 개선된 다익스트라 알고리즘의 시간 복잡도 👉 O(ElogV) (V는 노드의 개수, E는 간선의 개수)
- 개선된 다익스트라 알고리즘은 힙 자료구조를 사용
☝ 플로이드 워셜 알고리즘
- 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용하는 알고리즘
- 플로이드 워셜 알고리즘의 시간 복잡도 👉 O(N³)
- 플로이드 워셜 알고리즘은 다이나믹 프로그래밍
- 문제의 범위가 한정적인 경우(대략 500개 이하) 플로이드 워셜 알고리즘을 사용하고,
이상인 경우 다익스트라 알고리즘을 사용한다.
반응형
'내가 공부하려고 올리는 > TIL' 카테고리의 다른 글
2022-08-03 TIL(프로세스, 스레드, 스케줄러, CPU 스케줄러) (0) | 2022.08.03 |
---|---|
2022-08-02 TIL (0) | 2022.08.02 |
2022-07-29 TIL (0) | 2022.07.30 |
2022-07-27 TIL (0) | 2022.07.27 |
2022-07-26 TIL (0) | 2022.07.27 |
댓글