728x90
다익스트라
1. 하나의 정점에서 출발하여 다른 모든 정점으로의 최단거리
2. 시작 노드가 정해져 있는 상태에서 특정 노드까지의 거리를 구하는 경우
3. 음의 가중치 사용 불가
4. 시간복잡도 : 순차탐색 O(N^2), 우선순위큐 O(ElogV)
플로이드 와샬
1. 모든 정점에서 다른 모든 정점까지의 최단거리
2. 시작노드가 정해져 있지 않은 많은 경우를 고려해야하는 경우
3. 음의 가중치 사용 가능
4. 시간복잡도 : O(V^3)
5. n이 500이하인 경우가 대부분
6. 2차원 테이블에 값들 저장
반응형
댓글