[ALGO] Shortest Path

Shortest Path

최단 경로

• 말 그대로 가장 짧은 경로를 찾는 알고리즘 (길 찾기 문제!)
• 한 지점에서 특정 지점까지의 최단 경로를 구해야 하는 경우
• 모든 지점에서 다른 모든 지점가지의 최단 경로를 구해야 하는 경우
• 최단 경로 알고리즘은 주로 그래프로 표현하는데, 각 지점은 “노드”로 표현하고 노드 간 거리는 “간선”으로 표현
• 보통 코딩테스트에서는 최단 거리를 출력하도록 요구하는 문제가 많이 출제됨
• 대표적으로 다익스트라, 플로이드 워셜, 벨만 포드 알고리즘이 있음

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

• 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘
• 음의 간선이 없을 때 정상적으로 동작 (현실 세계의 길은 음의 간선으로 표현되지 않으므로 다익스트라 알고리즘은 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택)
• 기본적으로 그리디 알고리즘으로 분류 (매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복)

다익스트라 알고리즘의 원리

1. 출발 노드를 설정한다
2. 최단 거리 테이블을 초기화한다.
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
5. 위 과정에서 3,4번을 반복한다.

EX. 1번 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 경우

STEP 1. 초기 상태에서 다른 모든 노드로 가는 최단 거리를 “무한”으로 초기화한다. 출발노드에서 출발노드로의 거리는 0이므로 1번 노드의 거리는 0으로 초기화한다. 이 때 파이썬에서 무한은 int(1e9)로 표현한다. 먼저 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하는데, 출발 노드에서 출발 노드로의 거리는 0이므로 처음에는 출발 노드가 선택된다.

STEP 2. 이제 1번 노드를 거쳐 다른 노드로 가는 비용을 계산한다. 새로운 노드에 대해서 더 짧은 경로를 찾게 되면 거리를 업데이트시킨다. 이 경우는 2번, 3번, 4번 노드를 업데이트하게 된다.

STEP 3. 이후의 모든 단계에서도 마찬가지로 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 따라서 4번 노드가 선택된다. 이 때 4번 노드까지의 최단 거리는 1이므로 4번 노드를 거처셔 3번과 5번 노드로 가는 최송 비용은 차례대로 4(1+3), 2(1+1)이다. 이 두 값은 기존의 리스트에 담겨 있던 값보다 작으므로 갱신된다.

STEP 4. 2번 노드가 선택된다. 2번과 5번 노드까지의 최단 거리가 2로 값이 같은데, 이럴때는 일반적으로 번호가 작은 노드를 선택한다. 이번 단계에서 2번 노드를 거쳐서 가는 경우, 현재의 최단 거리를 더 짧게 갱신할 수 있는 방법은 없다.

STEP 5. 5번 노드가 선택된다. 5번 노드까지의 최단거리가 2이므로 5번 노드에서 3번 노드로 가는 거리인 1을 더한 3이 기존 값인 4보다 작기 때문에 갱신된다. 6번 노드로 가는 경우도 마찬가지로 4로 갱신된다.

STEP 6. 이어서 3번 노드를 선택한 뒤에 동일한 과정을 반복한다.

STEP 7. 마지막으로 6번 노드를 선택한 뒤에 동일한 과정을 반복한다. 지금까지의 최종 최단 거리 테이블은 다음과 같다.

다익스트라 알고리즘 해석

• 최단 거리 테이블이 의미하는 바는 1번 노드로부터 출발했을 때 2번, 3번, 4번, 5번, 6번 노드까지 가지 위한 최단 경로가 각각 2,3,1,2,4라는 의미이다.
• 다익스트라 알고리즘에서는 “방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택”하는 과정을 반복하는데, 이렇게 선택된 노드는 “최단 거리”가 완전히 선택된 노드이므로, 더 이상 알고리즘을 반복해도 최단거리가 감소하지 않는다.
• 즉, 다익스트라 알고리즘이 진행되면서 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해할 수 있다.
• 따라서 사실 마지막 노드에 대해서는 해당 노드를 거쳐 다른 노드로 가는 경우를 확인할 필요가 없다.

다익스트라 알고리즘의 시간 복잡도

• O(ElogV) : E -> 간선의 개수, V -> 노드의 개수
• 힙 자료구조 사용