목록최단거리 (1)

하루살이 개발자

[알고리즘] 최단 경로 알고리즘(1) - 다익스트라(Dijkstra) 알고리즘

최단 경로 알고리즘이란, 주어진 노드와 간선(edge)들 중, 가장 짧은 경로를 찾는 알고리즘입니다. 즉, 서울에서 인천, 대전, 광주, 부산을 갈 수 있는 가장 짧은 경로를 찾는 것입니다. 0. 최단 경로 문제 - 다익스트라 알고리즘 이용(BFS 너비 우선 탐색) - "우선 순위 큐( 최소 힙 방식)"을 이용하여, 시간 복잡도 O(nlogn) - 이동경로가 양수라 하면 Dijkstra 알고리즘, 음수를 포함한다면 Bellman-ford 알고리즘 사용! * 다익스트라 알고리즘 1. 출발 노드를 설정 2. 최단 거리 테이블을 초기화(그러므로 최단 거리를 기록할 테이블을 정의해야 함) 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택(방문하지 않은 노드를 체크해야 하므로 이를 위한 테이블을..
CS/알고리즘 2022. 2. 13. 09:26
이전 Prev 1 Next 다음