알고리즘) 최단 경로 알고리즘

가장 짧은 경로를 찾는 알고리즘

1. 한 지점에서 다른 지점까지의 최단 경로

2. 한 지점에서 다른 모든 지점까지의 최단 경로

3. 모든 지점에서 다른 모든 지점까지의 최단 경로

 

-> 각 지점은 그래프에서 노드로 표현

-> 연결된 도로는 그래프에서 간선으로 표현

 

다익스트라 알고리즘(최단경로)

- 특정한 노드에서 모든 노드로 가는 최단 경로를 계산

- 음의 간선이 없을 때 정상적으로 동작

-> 현실 세계에서는 음의 간선으로 표현되지 않는다

다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류

-> 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정 반복

-> 길찾기 문제는 다이나믹 프로그래밍을 사용한다

 

순서

1. 출발 노드 설정

2. 최단 거리 테이블 초기화

3. 방문하지 않은 노드 중에서 최단 거리가 짧은 노드 선택

4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블 갱신

5. 3,4 번 반복

 

동작 과정에서 최단 거리 테이블은 각 노드에 대한 현재까지의 최단 거리 정보를 가지고 있다

처리과정에서 더 짧은 경로를 찾으면 최단 거리 경로 갱신

이미 방문 처리된 노드는 최단거리가 구해진 것이기 때문에 더이상 갱신하지 않는다

-> 이 부분이 다이나믹 프로그래밍이 적용된 것

-> 마지막 노드는 이동이 완료된 것이기 때문에 계산하지 않는다

 

매 상황 가장 비용이 적게 드는 노드를 선택해 반복 (그리디 알고리즘)

한 번 처리된 노드의 최단 거리는 고정되어 바뀌지 않음

 

완벽한 형태의 최단 경로까지 구하려면 추가 기능을 넣어야함

-> 단계마다 방문하지 않은 노드를 선택하기 위해 1차원 테이블의 모든 원소를 순차 탐색

 

시간 복잡도는 0(V^2) -> 매번 선형 탐색을 해야하기 때문

-> 전체 노드의 개수가 5000개 이하라면 해결 가능

 

 

 

다익스트라 알고리즘 개선

-> 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택하기 위해 힙 자료구조(최소 힙)를 이용

-> 전체 동작은 동일하지만 선형 시간이었던 탐색 시간을 O(logN)까지 줄일 수 있음

 

이미 처리가 끝난 원소는 테이블에 기록된 값과 비교할 수 있도록 처리 (최단 거리 테이블과 비교)

 

최대 간선의 수를 E라고 할 때,

힙을 이용하는 다익스트라 알고리즘 시간 복잡도는 O(ElogE)

중복 간선이 포함되지 않는다면 O(ElogV)