728x90
반응형
다익스트라 dijstra
그래프에서 최단 거리를 구하는 알고리즘
출발 노드와 모든 노드 간에 최단 거리 탐색
( = 특정 노드와 다른 노드 사이 최단 거리를 구하는 경우 효율적)
에지는 모두 양수
1. 그래프 구현하기
2. 최단 거리 리스트 초기화하기
최단 거리 리스트 생성
출발 노드 0, 이외 노드 모두 무한으로 초기화
3. 값이 가작 작은 노드 고르기
최단 거리 리스트에서 현재 값이 가장 작은 노드 선택
4. 최단 거리 리스트 업데이트 하기
선택 노드에 연결된 에지 값을 바탕으로 다른 노드 값 업데이트
Min(선택 노드의 최단거리 리스트 값 + 에지 가중치, 연결 노드의 최단 거리 리스트 값)
5. 3, 4반복
반응형
