가장 빠른 길 찾기

최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘이다.

예를 들어, ‘한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우’,

‘모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우’ 등 다양하다.

최단 경로 알고리즘은 다음과 같이 나눌 수 있다.

• 다익스트라 최단 경로 알고리즘
• 프로이드 워셜
• 벨만 포드 알고리즘

그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 최단 경로 알고리즘에 그대로 적용된다는 특징이 있다.

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

다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때

특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.

다익스트라 최단 경로 알고리즘은 ‘음의 간선’이 없을 때 정상적으로 동작한다.

매번 ‘가장 비용이 적은 노드’를 선택해서 임의의 과정을 반복하기 때문에 기본적으로 그리디 알고리즘을 분류된다.

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

다익스트라 알고리즘은 최단 경로를 구하는 과정에서 ‘각 노드에 대한 현재까지의 최단 거리’ 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한다는 특징이 있다.

이러한 1차원 리스트를 최단 거리 테이블이라 한다.

다익스트라 알고리즘을 구현하는 방법은 2가지이다.

방법1) 구현하기 쉽지만 느리게 동작하는 코드 
방법2) 구현하기에 조금 더 까다롭지만 빠르게 동작하는 코드

다익스트라 예제

1번 노드에서 다른 노드로 가는 비용을 계산하자.

이후 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택해야 한다.

1번 에서 최단 거리가 가장 짧은 4번 노드가 선택된다.

최단 거리 테이블을 또 갱신해보자.

2, 5번 노드의 최단 거리 값이 같은데, 이럴 때는 일반적으로 번호가 작은 노드를 선택한다.

2번 노드를 선택했으나 현재 최단 거리 테이블에서 변경되는 것은 없다.

2번 노드 다음으로 5번 노드가 선택된다.

현재 5번 노드까지 가는 최단 거리가 2이므로 3번, 6번 노드의 값이 다음과 같이 갱신된다.

최단 거리 테이블이 의미하는 것은 1번 노드부터 출발했을 때

2, 3, 4, 5, 6번 노드까지의 최단 경로가 각각

2, 3, 1, 2, 4 라는 의미다.

다익스트라 최단 경로 알고리즘에서 ‘방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택’하는 과정을 반복하는데, 이렇게 선택된 노드는 ‘최단 거리’가 완전히 선택된 노드이므로, 더 이상 알고리즘을 반복해도 최단 거리가 줄어들지 않는다.

방법1. 간단한 다익스트라 알고리즘

간단한 다익스트라 알고리즘은 O(V^2)의 시간 복잡도를 가지며, V는 노드의 개수를 의미한다.

각 노드에 대한 최단 거리를 담는 1차원 리스트를 선언하고

단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해

매 단계마다 1차원 리스트의 모든 원소를 확인(순차 탐색)한다.

이 방법은 매번 선형 탐색, 현재 노드와 연결된 노드를 매번 일일이 확인하기 때문에

총 노드의 개수가 5000개 이하아면 괜찮다.

그런데 10000개를 넘어가거나 간선의 개수가 많을 때는 다음 방법을 이용해야 한다.

방법2. 개선된 다익스트라 알고리즘

이 방법은 최단 경로 문제를 최악의 경우에도 시간 복잡도 O(Elog V)를 보장하여 해결할 수 있다.

V는 노드 개수, E는 간선의 개수이다.

이전에는 매번 최단 거리 테이블을 선형적으로 탐색했는데

단순히 선형 탐색을 하는 것이 아니라 더욱더 빠르게 찾을 수 있다면?

개선된 다익스트라 알고리즘에서는 힙(heap) 자료구조를 사용한다.

힙을 사용하면 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아 처리하므로

출발 노드로부터 가장 거리가 짧은 노드를 더욱 빠르게 찾을 수 있다.

힙 자료구조는 우선 순위 큐를 구현하기 위해 사용하는 자료구조 중 하나이다.

우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 점이 특징이다.

우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다.

예) 여러 개의 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건 데이터부터 꺼내서 확인해야 하는 경우

단계별로 우선순위 큐가 어떻게 변하는지 알아보자.

우선순위 큐를 적용해도 다익스트라 알고리즘이 동작하는 기본 원리는 동일하다.

최단 거리를 저장하기 위한 1차원 리스트(최단 거리 테이블)은 동일하다.

현재 가장 가까운 노드를 저장하기 위한 목적으로만 우선순위 큐를 추가로 이용한다고 보면 된다.

1단계)

다시 1번 노드부터 출발해보자.

여기서는 다음과 같이 출발 노드를 제외한 모든 노드의 최단 거리를 무한으로 설정한다.

이후 우선순위 큐에 1번 노드를 넣는데 [거리: 0, 노드: 1] 이 정보를 갖는 객체를 우선순위 큐에 넣으면 된다.

우선순위 큐에 넣으면 거리순으로 정렬된다.

우선순위 큐: (거리: 0, 노드: 1)

거리가 가장 짧은 노드를 선택하기 위해 우선순위 큐에서 노드를 꺼내면 된다.

해당 노드를 이미 방문한 적이 있다면 무시하고,

처리한 적이 없으면 1번 노드를 거쳐서 2, 3, 4 노드로 가는 최소 비용을 계산한다.

우선순위 큐: (거리: 0, 노드: 1) (거리: 2, 노드: 2) (거리: 5, 노드: 3)

2단계)

이번에는 [1, 4]의 값이 꺼내진다.

아직 4번 노드에 방문한 적이 없으므로 노드 4를 기준으로 연결된 간선들을 확인한다.

1 > 4 > 3과 1 > 4 > 5 경로의 최소 비용은 기존 테이블의 값들보다 작기 때문에 테이블이 갱신된다.

우선순위 큐: (거리: 2, 노드: 2) (거리: 2, 노드: 5) (거리: 4, 노드: 3) (거리: 5, 노드: 3)

3단계)

다음으로 선택되는 노드는 2번 노드이다.

2번 노드를 거쳐서 가는 경우 중 최단 거리를 더 짧게 갱신할 수 있는 방법이 없기 때문에 다음 단계로 넘어간다.

4단계)

이번엔 5번 노드를 꺼냈다.

5번 노드에서는 3, 6번 노드로 갈 수 있고 5번 노드를 거치는 경우

최단 거리가 줄어들기 때문에 테이블이 다음과 같이 갱신된다.

우선순위 큐: (거리: 3, 노드: 3) (거리: 4, 노드: 3) (거리: 4, 노드: 6) (거리: 5, 노드: 3)

5단계)

다음으로 [거리: 3, 노드: 3]을 꺼낸다.

이 경우 최단 거리 테이블이 갱신되지 않는다.

6단계)

다음으로 [거리: 4, 노드: 3]을 꺼낸다.

3번 노드는 앞서 처리된 적이 있다.

이미 처리되었기 때문에 무시한다.

7단계)

이어서 [거리: 4, 노드: 6]이 꺼내진다.

우선순위 큐: (거리: 5, 노드: 3)

8단계)

마지막 원소도 확인해보니 이미 처리된 노드이므로 무시한다.

모든 단계를 거치고 최단 거리 테이블에 남아 있는 0, 2, 3, 1, 2, 4가 각 노드로의 최단 거리이다.

2) 플로이드 워셜 알고리즘

다익스트라 알고리즘은 ‘한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우’에 사용할 수 있는 최단 경로 알고리즘이다.

플로이드 워셜 알고리즘은 ‘모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야 하는 경우’에 사용할 수 있는 알고리즘이다.

다익스트라 알고리즘은 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택한다.

그리고 해당 노드를 거쳐 가는 경로를 확인하며, 최단 거리 테이블을 갱신하는 방식으로 동작한다.

플로이드 워셜 알고리즘도 단계마다 ‘거쳐 가는 노드’를 기준으로 알고리즘을 수행한다.

매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다는 점이 다르다.

또한 점화식에 맞게 2차원 리스트를 갱신하기 때문에 다이나믹 프로그래밍으로 볼 수 있다.

각 단계에서는 해당 노드를 거쳐 가는 경우를 고려한다.

예를 들어 1번 노드에 대해 확인할 때 1번 노드를 중간에 거쳐 지나가는 모든 경우를 고려하는 것이다.

A > 1번 노드 > B로 가는 비용을 확인하고 최단 거리를 갱신한다.

A > B의 비용이 3이고 A > 1번 노드 > B로 가는 비용이 2이면 A > B의 이동 비용을 2로 갱신하는 것이다.

플로이드 워셜 알고리즘의 총 시간 복잡도는 O(N^3)이다.
따라서 N(노드)의 범위 값이 500 이하여야 한다.

플로이드 워셜 예제

위와 같은 그래프는 다음처럼 초기 테이블을 설정할 수 있다.

1단계)

1번 노드를 거쳐 가는 경우를 고려한다.

계산해야 할 값들은 다음과 같다.

D23 = min(D23, D21+D13)
D24 = min(D24, D21+D14)
D32 = min(D32, D31+D12)
D34 = min(D34, D31+D14)
D42 = min(D42, D41+D12)
D43 = min(D43, D41+D13)

1번을 제외한 2, 3, 4 노드에서 2개의 노드를 뽑는 방식으로

하나씩 확인하며 값을 계산하고 갱신하는 것인데

예를 들어 D23 = min(D23, D21+D13)은

‘기존의 2번에서 3번으로 가는 비용’ 보다 ‘2번에서 1번을 거쳐 3번을 가는 비용’이 더 작다면

갱신한다는 의미를 갖고 있다.

2단계)

이번에는 2번 노드를 거쳐 가는 경우를 계산한다.

노드의 개수가 총 4개이므로 4단계까지 수행한다.

최종 결과는 다음과 같다.

1번 노드에서 3번 노드로 가는 최단 거리가 8이라는 의미다.

예제 코드

• 간단한 다익스트라 알고리즘
• 개선된 다익스트라 알고리즘
• 플로이드 워셜 알고리즘