[알고리즘/Algorithm]최단경로(Shortest Path) (1)
최단경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘인데 보통 그래프, 간선, 노드로 표현된다.
우리는 보통 문제를 해결할 때 다익스트라 알고리즘, 플로이드 워셜, 벨만포드 알고리즘 이렇게 3가지를 이용하게 되는데 이 책에서는 2가지만 다루고 있다.
🔷 그래프, 노드, 간선
◼ 그래프(Graph)
그래프란 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료 구조를 의미한다.
◼노드(Node)
정점(Vertex)이라고도 부르며 단순하게 하나의 지점이라고 생각하면 편하고 다른 연결된 노드와 간선에 대한 정보를 가지고 있다.
◼간선(Edge)
노드와 노드 사이에 연결된 통로라고 생각하면 된다.
◼그래프의 표현
그래프의 표현은 크게 2가지 방식으로 표현할 수 있다. 0과 1 사이의 거리가 7이고, 0과 2 사이의 거리가 5인 그래프를 표현하는 예제이다.
◻ 인접행렬 (Adjacency Matrix) : 2차원 배열로 그래프의 연결관계를 표현하는 방식
◻ 인접리스트 (Adjacency List) : 리스트로 그래프의 연결관계를 표현하는 방식
🔷 다익스트라 알고리즘
여러개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 다익스트라 알고리즘은 '음의 간선' 이 없을 때 정상적으로 당작한다. 따라서 현실의 Gps 소프트웨어의 기본 알고리즘 등으로 채택된다. 원리는 아래와 같다.
1. 출발노드를 설정한다
2. 최단 거리 테이블을 초기화 한다.
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
5. 위 과정에서 3번과 4번을 반복한다.
* 다익스트라 알고리즘은 각 노드에 대한 현재까지의 최단거리 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한다는 특징이 있다. 다스트라 알고리즘의 구현방법은 2가지가 있다.
◼ 간단한 다익스트라 알고리즘
O(V^2)의 시간 복잡도를 가지는데 전체 노드의 개수가 10000개를 넘게되면 이 코드로는 문제 해결이 힘들다.
◼ 개선된 다익스트라 알고리즘
힙 자료구조를 이용하여 O(ElogV)의 시간복잡도를 가지게 되어 훨씬 빠르다.
- 힙(Heap) 자료구조란?
힙 자료구조는 우선순위 큐(Priority Queue)를 구현하기 위하여 사용하는 자료구조 중 하나이다. 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 점이 특징이다. 파이썬에서는 우선순위 큐가 필요할 때 PriorityQueue 혹은 heapq를 사용할 수 있는데 heapq가 일반적으로 빠르게 동작하기 때문에 권장되어진다. 기존 다익스트라 알고리즘과 다른점은 아래와 같다.
우선 순위 큐를 이용하여 큐에 가장 가까운 순서대로 노드 정보를 담고 하나씩 꺼내어 다른 노드들을 넣는다. 이미 처리된 노드 정보들은 무시한다.
◼ 참고
- 이것이 취업을 위한 코딩테스트다 with 파이썬