다익스트라 최단 경로
특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산
음의 간선이 없을 때 정상적으로 동작
매 상황에서 가장 비용이 적은 노드를 선택해 과정을 반복
동작과정
1. 출발노드 설정
2. 최단 거리 테이블 초기화
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
5. 3,4을 반복
한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않음
'알고리즘' 카테고리의 다른 글
| 0-1 BFS (0) | 2022.01.19 |
|---|---|
| 플로이드-워셜 ( Floyd-Warshall) (0) | 2022.01.19 |
| 다이나믹 프로그래밍 (Dynamic programming) (0) | 2022.01.19 |
| 구현 (Implementation) (0) | 2022.01.19 |
| DFS (Depth-First Search) 깊이 우선 탐색 (0) | 2022.01.19 |