| 기능 |
특징 |
시간 복잡도(노드 수: V, 에지 수: E) |
| 출발 노드와 모든 노드간의 최단 거리 탐색 |
에지는 모두 양수 |
O(ElogV) |
핵심 이론
1. 인접 리스트로 그래프 구현
- 인접 행렬로 구현해도 좋지만 시간 복잡도 측면, N의 크기가 클 것을 대비해 인접 리스트로 구현하는 것이 좋음
2. 최단 거리 배열 초기화
3. 값이 가장 작은 노드 고르기
4. 최단 거리 배열 업데이트
5. 과정 3~4를 반복해 최단 거리 배열 완성
- 과정 4에서 선택 노드가 될 때마다 다시 선택되지 않도록 방문 배열을 만들어 처리 → visited[]
