최단 경로 문제란?
- 가장 짧은 경로를 찾는 알고리즘을 의미한다.
- 다양한 문제 상황
- 한 지점에서 다른 한 지점까지의 최단 경로- 한 지점에서 다른 모든 지점까지의 최단 경로 -> 다익스트라 알고리즘
- 모든 지점에서 다른 모든 지점까지의 최단 경로 -> 플로이드 워셜 알고리즘
- 각 지점은 그래프에서 노드로 표현
- 지점 간 연결된 도로는 그래프에서 간선으로 표현
최단 경로 알고리즘 동작 과정
- 최단 거리 테이블은 각 노드에 대한 현재까지의 최단 거리 정보를 가진다.
- 처리 과정에서 더 짧은 경로를 찾으면 더 짧은 경로로 값을 갱신한다.
다익스트라 최단 경로 알고리즘이란?
- 특정 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다.
- 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다.
- 현실 세계의 간선은 음의 간선으로 표현되지 않는다.- 음의 간선이 표현될 때는 벨만 포드 알고리즘을 사용할 수 있다.
- 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류된다.
- 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다.
- 다익스트라 최단 경로 알고리즘은 그리디 알고리즘 유형에 속한다
- 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다. - 단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 더이상 바뀌지 않는다.
- 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해할 수 있다. - 다익스트라 알고리즘을 수행한 뒤에 테이블에 각 노드까지의 최단 거리 정보가 저장된다.
- 완전한 형태의 최단 경로를 구하려면 소스 코드에 추가적인 기능을 더 넣어야 한다.
다익스트라 최단 경로 동작 과정
- 출발 노드를 설정
- 최단 거리 테이블 초기화
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
-> 최단 거리 테이블을 직접 갱신하지 않고, 우선 순위 큐에 삽입하는 방식을 사용할 수도 있다. - 위 과정에서 3번과 4번을 반복
우선순위 큐
- 다익스트라 알고리즘은 우선 순위 큐를 사용하여 구현한다.
- 우선 순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료 구조이다.
- 예를 들어 여러 개의 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건 데이터부터 꺼내서 확인해야 하는 경우에 우선 순위 큐를 이용할 수 있다.
- 파이썬, 씨플플, 자바를 포함한 대부분의 프로그래밍 언어에서 표준 라이브러리 형태로 지원한다.
힙
- 우선순위 큐를 구현하기 위해선 힙 자료구조를 이용하여 구현할 수 있다.
- 최소 힙과 최대 힙이 있다.
- 다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 사용된다.
js의 힙 라이브러리
- js는 기본적으로 우선 순위 큐를 라이브러리로 제공하지 않는다.
- 최단경로 알고리즘 등에서 힙이 필요한 경우 별도의 라이브러리를 사용해야한다.
다익스트라 최단경로의 특징
- 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
- 이를 위해 힙 자료 구조를 이용한다. - 다시 말해, 현재 상황에서 가장 가까운 노드를 저장해 놓기 위해서 힙 자료구조를 이용한다.
- 현재의 최단 거리가 가장 짧은 노드를 선택해야 하므로 최소 힙을 사용한다.
다익스트라 알고리즘의 동작 과정
다익스트라 알고리즘의 시간 복잡도
- 힙 자료구조를 이용하는 다익스트라 알고리즘의 시간 복잡도는 O(ElogV)이다.
- 노드를 하나씩 꺼내 검사하는 반복문 (while)은 노드의 개수 V 이상의 횟수로는 처리되지 않는다.
- 결과적으로 현재 우선 순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 총 횟수는 최대 간선의 개수(E)만큼 연산이 수행될 수 있다. - 직관적으로 전체 과정은 E개의 원소를 우선 순위 큐에 넣었다가 모두 빼내는 연산과 매우 유사하다.
- 시간 복잡도 O(ElogV)로 판단할 수 있다.
- 중복 간선을 포함하지 않는 경우에 이를 O(ElogV)로 정리할 수 있다.
프론트엔드 개발자를 향해서