TIL 2024-08-05 다익스트라 알고리즘

 

다익스트라

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

 

1. 인접 리스트로 표현 배열의 자료형은 노드, 가중치

2. 최단 거리 배열 초기화 출발 노드 인덱스 0 / 나머지 무한

3. 값이 가장 작은 노드 선택

4. 선택된 노드에 연결된 에지의 값을 바탕으로 다른 노드의 값 업데이트

공식 Math.min(선택 노드 최단 거리 배열 값 + 에지 가중치, 연결 노드 최단 거리 배열의 값)

D[1] == 0 && D2[2] == 무한

1 -> 2 가중치 8

D[1] + 8 < D[2] -> D[2] 값 갱신