[ 그래프 ] 다익스트라(Dijkstra)

 다익스트라

그래프에서 최단 거리를 구하는 알고리즘

• 출발 노드와 모든 노드간의 최단 거리 검색
• 제약 조건 : 에지는 모두 양수
• 시간 복잡도는 O(ElogV)   V: 노드 수, E: 에지 수

 

💡  다익스트라 알고리즘의 핵심 이론

1. 인접리스트로 그래프 구현하기

배열의 자료형은 (노드, 가중치)

 

 

2. 최단거리 배열 초기화하기

출발노드는 0 이외 노드는 무한으로 초기화

 

 

3. 값이 가장 작은 노드 고르기

여기서는 값이 0인 출발 노드에서 시작

 

 

4. 최단 거리 배열 업데이트 하기

현재 선택된 노드의 에지들을 탐색하고 업데이트

-> Min(선택 노드의 최단 거리 배열의 값 + 에지 가중치, 연결 노드의 최단 거리 배열의 값)

 

5. 과정 3~4를 반복해 최단 거리 배열 완성하기

과정 4에서 이미 선택됐던 노드를 다시 방문하지 않기위해 방문 배열(visited)을 만든다.

 

☝🏻  다익스트라 알고리즘은 출발 노드와 그외 노드 간의 최단 거리를 구하는 알고리즘이다