다익스트라 알고리즘
2022. 8. 19. 08:48ㆍ코딩
https://namu.wiki/w/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#s-1
https://youtu.be/611B-9zk2o4
매상황에서 가장 비용이 적은 노드를 선택
-그리디 알고리즘의 한 종류
-특정 노드 출발, 다른 모든 노드로 가는 최단 거리
동작 과정
1. 출발 노드 설정
2. 최단 거리 테이블 초기화
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산해 최단 거리 테이블 갱신
5. 3,4번 반복
'코딩' 카테고리의 다른 글
| 백준 12865번 문제(평범한 배낭) 파이썬(Python) 풀이(배우는 단계) (0) | 2022.08.23 |
|---|---|
| 백준 1463번 (0) | 2022.08.23 |
| 백준 10773번 (0) | 2022.08.23 |
| 백준 2579번 (0) | 2022.08.23 |
| 플로이드 워셜 알고리즘 (0) | 2022.08.19 |